Прыжки по блокам

Задача: в каждой клетке написано, на сколько прыгать вперёд. Надо быстро отвечать, за сколько прыжков шарик вылетит за край, - при этом значения меняются.

Наивный проход - $O(n)$ на запрос. Двоичные подъёмы дали бы $O(\log n)$, но плохо переживают изменения: одно изменение портит таблицу для многих клеток.

Предпосчёт выхода из блока

Для каждой клетки $i$ храним три числа:

• $next[i]$ - первая клетка вне блока, куда мы попадём, прыгая из $i$;
• $steps[i]$ - сколько прыжков для этого нужно;
• $last[i]$ - последняя клетка внутри блока перед этим выходом.

Считается это одним проходом справа налево внутри блока: если прыжок из $i$ уже выводит за блок, то ответ тривиален, иначе он берётся у клетки $i + a[i]$, которая лежит правее и уже посчитана.

for (int i = right; i >= left; i--) {
    int to = i + a[i];
    if (to > right) { next[i] = to; steps[i] = 1; last[i] = i; }
    else            { next[i] = next[to]; steps[i] = steps[to] + 1; last[i] = last[to]; }
}

Порядок обязателен: слева направо не сработает, потому что нужная клетка окажется ещё не посчитанной.

Запрос и обновление

Запрос: прыгаем не по клеткам, а по блокам. Каждый прыжок по $next$ выводит из текущего блока, значит их не больше $n / B$.

Обновление: изменили $a[i]$ - испортился только его блок, потому что $next$ внутри блока зависит лишь от клеток того же блока. Пересчитываем блок за $O(B)$.

Оба действия - $O(\sqrt{n})$.

Почему это общий приём

Схема работает для любого «прыжка вперёд по фиксированному правилу»: клетки с шагами, ссылки на следующий элемент, переходы автомата. Существенны два свойства:

1. прыжок всегда вперёд - иначе предпосчёт справа налево не замкнётся;
2. изменение одной клетки портит только её блок.

Если прыжки могут вести назад, появляются циклы, и приём ломается: выход из блока может не существовать.