[Solved]: Segment trees with insertion/deletion

Problem Detail: 

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?

Asked By : matheuscscp

Answered By : Paras Meena

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/43146