Sparse tables, двоичный подъем

Теория на хабре
Еще теория
Более продвинутая структура, нужна не так часто: Disjoint sparse tables