RMQ with DSU in almost constant time?

Revision en1, by Jakube, 2018-01-22 19:55:42

On the e-maxx website about the Disjoint Set Union data structure there is a paragraph about computing range minimum queries offline using DSU. (http://e-maxx.ru/algo/dsu#15)

It is claimed that it works in O(α(n)) time per query on average (α is the inverse Ackerman function).

My Russian is terrible, and Google/Yandex translate also is quite hard to understand for this paragraph. So I have some questions about this one.

From what I can understand using Google translate is the following:

  • this only works if the elements are actually a permutation of 1 to n (otherwise we would have to sort the elements beforehand)
  • for each index in the array we store the reference to the closest query that ends right of the index.

From this information I was able to construct this tree/forest structure. (red are the range queries, blue arrows are the references that point to the parent)

Now the algorithm then goes as follows:

  • We start with the empty array.
  • We insert the smallest number 1 and follow the references. In that way we visit all range queries where 1 is the answer.
  • Then

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English Jakube 2018-01-22 20:31:12 202 (published)
en2 English Jakube 2018-01-22 20:26:44 1409
en1 English Jakube 2018-01-22 19:55:42 1240 Initial revision (saved to drafts)