Segment trees with insertion/deletion

Question

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 know something about that?

Answer 1

Similar to what you asked, this Problem on the maximum height of solders involves range queries and insertions of elements.

I solved that problem using treap, which can be used to solve your problem as well.

Here is a very brief introduction to treap.

A Cartesian tree is just a binary tree on a sequence of pairs that is

• a heap if we look at only one element of each pair, and
• a binary search tree if we look at the other element of each pair.

In a Cartesian tree, if we assign random values to each heap-ordered element, then the expected height of the resulting tree is $O(\log n)$. This is the idea behind treaps.