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)
"if we have more spaces, we will need to rearrange in order to distance between adjacent elements as large as possible". You should explain more clearly about this. For example, if our node size is 8 and we have 6 inserted places, how can you distribute them?
You also should consider the case in which we need to insert a new number to the first place 2^k times. I think that your algorithm will be slow on this.
Put x elements into k position:
b[] is best when it meets following condition:
This approach reminds me of the Scapegoat Tree...