Segment tree with easy shifting

Question

I need Data Structure based on Segment Tree, but with one difference to clasical segment tree. DS should support easy shifting of elements. I mean I would like to have ds on which I could:

• make queries on segments (i.e. sum of elements from index l to index r)
• insert new elemnts before any index and then shift all elements on the right side of new elements

It will be nice if all these operations will work in O(logn) Greetings

Answer 1

Yes, but not sure you can keep the tree balanced.

The basic structure is like this. Every node keeps track of only the distance between the start of the interval it keeps track of and the split between its children. For example if a node keeps the interval [A, B] and has children keeping [A,C] and [C+1, B] then the first node should only store the information C - A. This will allow you to easily change the sizes of the intervals without having to mess with the entire structure. This also means that you invalidate any existing iterators when you shift anything inside and that each iterator keeps track of the interval.

To do a shift operation:

• do a search for the insertion point.
• pick an appropriate node on the path.
• insert a new node above the selected node. This nodes should contain the old + new interval. So set it's split value to the size of the shift. Now the new space is the left child the old space is the right child.
• add any children you want to keep for the new space.
• update all the parents where the split point was on the left since now there are more values before their split.

Any other operation should be done the same. You should pick a node where the new interval is roughly equal to the size of the node so that you keep the O(logn) for operations. Obviously inserting 1 element over and over again can cause some paths to be considerably longer than others, unless you also add a step to rebalance the tree after you do a shift.

However, if you know the shifts before, I would simply go through the shifts backwards and compute the final location of all the data and queries O(N). Then you can simply do a regular segment tree and not worry about the shifts.