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