Rating changes for the last round are temporarily rolled back. They will be returned soon. ×

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 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 O(n) method 3788 3920 3610

#### History

Revisions

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