(This blog has been restored as Errichto and some other users had wanted.)
Hi !
Here is some implementation for solving RMQ (Tarjan’s algorithm) (Range Maximum / Minimum Query).
It’s very simple to implement and it’s time complexity is O((n + q)·a(n)), a() stands for Akerman inverse function used in DSU.
Problem : Given array a of n integers, and q queries, for each query print the maximum value in range [L, R].
Solution: We need a array of vectors, called assigned. assigned[r] contains queries that their R is r. When getting queries, push each query in assigned[R]. We need a dsu, first pari is i. We need a stack, named st.
For i from 0 to n, do:
While st is not empty and a[st.top] <= a[i]
Set i parent of st.top in dsu and pop this element from st.
Push i to st
For each query assigned to i
Answer of this query is a[root of L of this query in DSU].
Note that in above code I used path-compression technique for dsu only, size-comparing technique can be used too (but it has lower performance).
It’s obviously true, because each time for any j ≤ i, a[root(j)] is the greatest value in range [j, i].
Performance test
Here is the result:
| Method\Time(milliseconds) | Strictly increasing array | Strictly decreasing array | Random |
| This method (known as Arpa's trick) | 2943 | 2890 | 2946 |
| Sparse table | 3612 | 3595 | 3807 |
| Vector + Binary search | 3101 | 6130 | 3153 |
