Коты в коробочках, или Компактные структуры данных

Ок :)

Коты в коробочках, или Компактные структуры данных

С этим я не спорю. Но всё же мне кажется, что select нельзя назвать обратной для rank операцией (т.к. описанное условие выполняется не всегда).

Коты в коробочках, или Компактные структуры данных

Внимательный читатель заметит, что select — обратная операция для rank. Если rank1(5) = 4, то select1(4) = 5.

Да? Но ведь rank1(2) = 1, а select1(1) = 0.