Some method for solving RMQ

Revision en1, by Arpa, 2016-12-11 13:20:07

(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].

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)