### Arpa's blog

By Arpa, history, 3 years ago, ,

(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

• +89

 » 3 years ago, # |   +61 I know this technique as "Arpa's trick". Are you sure you've got the right name?
•  » » 3 years ago, # ^ |   +28 I discovered this technique myself, but it seems this technique existed before (as Zlobober said). So I can't name this technique "Arpa's trick", but I call it "Arpa's trick", you can call it "Arpa's trick" as well.
•  » » 3 years ago, # ^ |   0 At least he's helping others ... You can also write tutorials and name techniques using your fake name . Are you sure you wrote "lucian bicsi" correctly ?
•  » » » 3 years ago, # ^ |   0 Fake name ?! In fact, "Arpa" is compressed version of my name, my real name is "AmirReza PoorAkhavan", my friends call me Arpa at school, chat, etc. I'm more familiar with "Arpa" instead of my real name ("PoorAkhavan" or "AmirReza").There are much persons, knowing me as "Arpa", and don't know my real name even.
•  » » » » 3 years ago, # ^ |   +8 I was talking about I_love_Retrograd
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 Oh right ! But your comment prepared a opportunity for me to talk about my nick name :DEdit: sorry anyway.
 » 3 years ago, # |   +6 You could also binary search on the stack instead of using DSU, which might be easier to code depending on the implementation, and still achieve a reasonable performance (binary searches are pretty light).
•  » » 3 years ago, # ^ | ← Rev. 2 →   +1 I'll add some statistics about what method is faster soon, please wait for several hours.Edit: Done.
»
3 years ago, # |
+5

You can outline header of the table like this:

A/B 1 2 3 4
Arpa's trick 1 3 6 0
Sparse table 6 3 1 0
O(n) 3 1 6 0

Code:

A/B | 1 | 2 | 3 | 4
- -
Arpa's trick | 1 | 3 | 6 | 0
Sparse table | 6 | 3 | 1 | 0
O(n) | 3 | 1 | 6 | 0