Прыжковые указатели: линейная память

Двоичные подъёмы хороши всем, кроме памяти: $O(n \log n)$ и промахи по кэшу. Есть конструкция с $O(n)$ памяти и той же оценкой на запрос.

Идея: хранить для каждой вершины всего два указателя — на родителя и один «длинный прыжок». Подъём делаем жадно: пробуем длинный прыжок, если он перелетает цель — шагаем к родителю.

Корректность очевидна: в худшем случае мы просто идём по родителям. Весь вопрос в том, как выбрать прыжки, чтобы шагов было мало.

Правило

void setJump(int v, int p) {
    par[v] = p;
    if (p == -1) { jmp[v] = v; return; }
    int j = jmp[p], b = jmp[j];
    if (dep[j] - dep[b] == dep[p] - dep[j]) jmp[v] = b;   // два равных прыжка подряд
    else jmp[v] = p;                                       // иначе — просто родитель
}

Читается так: если из родителя ведёт прыжок, а из его конца — прыжок такой же длины, склеиваем их в один прыжок двойной длины. Иначе довольствуемся шагом на единицу.

На бамбуке получается картина вида $1, 1, 3, 1, 1, 3, 7, 1, 1, 3, 1, 1, 3, 7, 15, \ldots$ — длины прыжков растут, но не монотонно.

Почему это логарифм

Доказательство держится на трёх утверждениях.

Прыжки не пересекаются частично — только вложены или не пересекаются вовсе. Индукция: прыжок из $v$ либо ведёт в родителя (тогда пересечь ничего не может), либо склеен из двух прыжков, для которых свойство уже доказано.

Не бывает трёх одинаковых прыжков подряд. Если бы были, то по правилу третий склеился бы, а не остался прежней длины.

После прыжка следующий прыжок не короче. Следствие предыдущего пункта.

Отсюда подъём распадается на две фазы. Пока прыжки не перелетают цель, их длины не убывают, а трёх одинаковых подряд не бывает — значит, за $2\log n$ шагов длина удваивается достаточное число раз. Когда прыжок начал перелетать, длины симметрично убывают, и это ещё $2\log n$. Грубая оценка сверху — $4\log n$.

Сколько на самом деле

Измерено на бамбуке — худшем случае для подъёмов:

$n$	шагов в худшем случае	$\log_2 n$	отношение
1 000	24	9	2,7
10 000	31	13	2,4
100 000	39	16	2,4
1 000 000	46	19	2,4

Реальная константа — около 2,4, а не 4. Оценка из доказательства грубая, как и положено оценке сверху.

LCA на прыжковых указателях

Оба способа из статьи про двоичные подъёмы переносятся дословно. Вот симметричный:

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    u = levelAncestor(u, dep[u] - dep[v]);      // выравниваем высоты
    if (u == v) return u;
    while (par[u] != par[v]) {
        if (jmp[u] != jmp[v]) { u = jmp[u]; v = jmp[v]; }   // прыжок не перелетает
        else                  { u = par[u]; v = par[v]; }   // перелетает — шаг
    }
    return par[u];
}

Синхронность работает по той же причине, что и раньше: вершины на одной высоте, поэтому и прыжки из них одинаковой длины.

Проверено: 20 000 деревьев, 1 883 353 запроса LCA и все запросы Level Ancestor — совпало с подъёмом по родителям.

Когда это нужно

Честно говоря, редко. Обычные двоичные подъёмы проще и на типичных ограничениях работают нормально.

Прыжковые указатели берут, когда $n$ большое и память в обрез, либо когда $n \log n$ ячеек перестают помещаться в кэш и константа становится решающей. Полезно знать, что такая возможность есть.