I discovered a brand new approach to implement insert operator on segment tree.

1. Advantages and disadvantages

There are following advantages:

• You don't need to know what is tree rotation.
• Run extremely fast in weak tests / random test cases.

There are following disadvantages:

• Complexity of each query is O(log^2 max(n)) (amortized)
• Source code is not shorter than source using balanced tree.

This is example code for impatient people: http://paste.ubuntu.com/8148477/

Because of its complexity, I got TLE in this problem: http://www.spoj.com/problems/QMAX3VN/

Before coding this structure, I thought it will be short, but it is not. However, I want to share with you this structure because I think idea used inside this structure is nice.

2. Properties

• Size of segment tree is fixed
• In each node, we maintain two values Max and Count, if u is not leaf, Max[u]=max(Max[u*2], Max[u*2+1), Count[u]=Count[u*2]+Count[u*2+1].
• Distance between two adjacent is quite long, for example: ----100-----200-----300---- where a - means unused space.
• The longer distance between two adjacent elements were, the faster queries executed.

3. Insertion

To insert an element valued into k-th position (to be more precise operator insert(k, X) means insert X between (k-1)-th element and k-th element), we find a suitable space to put it in. If we can't find any space, re-arrange a node.

This following example will make you understand.

Firstly, segment tree is empty:

-------------

Insert 1 5: we will insert 100 into middle position:

------5------

Insert 1 6: the most suitable position is 3rd position:

--6---5------

Insert 2 7: choose middle position between element 5 and element 6:

--6-7-5------

Insert 3 8: insert 8 between 7 and 5:

--6-785------

Insert 4 9: we cannot insert 9 between 8 and 5 right now, we must rearrange a node. Let's imagine the tree:

((--6-)(785))((---)(---))

It is impossible to insert 9 between 8 and 5 because node (785) is filled, we will rearrange its parent — node ((--6-)(785)) — as follow:

• Write its elements into a line: 6, 7, 8, 5
• Insert 9 between 8 and 5: 6, 7, 8, 9, 5
• Put elements in suitable places: ------- -> -678-95, if we have more spaces, we will need to rearrange in order to distance between adjacent elements as large as possible, for example: ----------------------------- -> ----6----7----8----9----5----.

4. Accessing k-th element

• Use value Count in each node to access k-th element in O(log n)

5. Get max of range L..R

• Execute this query as other segment trees.

6. Prove the complexity

• In worst cases, each queries run in (log n)^2 amortized.
• Almost actions work in O(log n), but operator "re-arrange".

In node which have length L, we execute maximal log L operator "re-arrange", the first time occur when number of empty spaces is L/2, the second time is L/4, ...

Complexity to re-arrange a node length L is O(L).

• There is 1 node length n: O(n log n) * 1
• There is 2 nodes length n/2: O((n/2) log n) * 2 = O(n log n)
• There is 4 nodes length n/4: O((n/4) log n) * 4 = O(n log n)
• ...

In conclusion, complexity to execute n operators insert is O(n (log n)^2)