Some method for solving RMQ

Revision en4, by Arpa, 2016-12-15 11:52:11

(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 + qa(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].
Code here.

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

This method (known as Arpas trick)
Vector + Binary search
Sparse table
O(n) method
generator

Here is the result:

Method\Time(milliseconds)Strictly increasing arrayStrictly decreasing arrayRandom
This method (known as Arpa's trick) 294328902946
Sparse table 361235953807
Vector + Binary search 310161303153
O(n) method 378839203610

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English Arpa 2016-12-15 11:52:11 6398 Added O(n) method
en3 English Arpa 2016-12-12 21:03:24 3862 Tiny change: '\nMetho' -trtd
en2 English Arpa 2016-12-11 13:23:12 3
en1 English Arpa 2016-12-11 13:20:07 2174 Initial revision (published)