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