I have a range query problem to solve. This problem requires not only range queries and update, but also insert or delete an element of the array. There is a series of operations that must be done in the order that they appear in the input. The operations can be one of the following: update a position of the array with a new value, insert a new element at some index of the array, remove an element at some index of the array and query information about a range of the array.

I tried an implementation of Segment Tree where the nodes are stored in an array. Left child of node at index p is at index 2p, right child is at index 2p + 1. This implementation is not enough, because the tree is static. All I can do are range queries and update positions of the original array. Inserting or deleting elements in the original array requires the tree to be rebuilt, so the running time is O(n) (too slow for the test cases). My program is correct, but too slow.

I Googled about Segment Trees with insertion/deletion and I read that is possible to do that with self-balancing binary search trees, like AVL or Red-Black trees. But I'm having trouble to understand how insertion or deletion would work in this dynamic Segment Tree that I need.

Does anybody knows something about that?

  • 1
    $\begingroup$ "Does anybody knows something about that?" is not a very specific question. Try to make your question specific - what in particular about dynamic segment trees don't you understand? Check out How to Ask. $\endgroup$
    – jbapple
    Mar 21 '16 at 12:52

I think this Problem is same as you asked and i solved this problem using Treap .

  • 7
    $\begingroup$ Please at least summarize the linked page here. Links break all the time and, if that link goes away, there'll be nothing left in your answer. We're trying to be a question and answer site, not a link farm. $\endgroup$ Mar 21 '16 at 15:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.