Succinct структуры, деревья и скобочные последовательности

Формально, succinct-структуры — это такие, которые используют $\mathcal{o}(N)$ дополнительной памяти для обеспечения операций над множеством из $N$ бит. Неформально — это несколько способов хранения дерева размера $N$ за $2N + \mathcal{o}(N)$ бит и использования этих $\mathcal{o}(N)$ для навигации по деревьям, а иногда и для ответов на довольно сложные запросы.

Одно из подобных битовых представлений вы, с большой вероятностью, встречали: делаем обход в глубину, каждый раз, когда опускаемся, записываем «(», когда поднимаемся — «)». В результате мы должны получить правильную скобочную последовательность длины $2N-2$. В целом, вот эти $2N$ бит, но что можно делать с таким представлением? Как оказывается, всё, что нам обычно нужно от дерева, можно получить с помощью небольших вспомогательных вычислений. А сами succinct-деревья очень даже практичны, особенно, когда число узлов переваливает за миллион.