Спуск по дереву

Половина задач спрашивает не «сколько», а «где»: где $k$-й ноль, где первый элемент не меньше $x$, где $k$-й ещё не удалённый.

Первое, что приходит в голову, — двоичный поиск по ответу: проверяем «сколько нулей на префиксе до $m$» запросом к дереву и ищем нужное $m$. Работает, но стоит $O(\log^2 n)$.

Спуск делает то же за один логарифм.

Спуск по аддитивной величине

Стоя в узле, мы уже знаем ответ для каждой половины. Значит выбор, куда идти, делается на месте — без нового запроса:

int kthZero(int v, int tl, int tr, int k) {
    if (tl == tr) return tl;
    int tm = (tl + tr) / 2;
    if (tree[2 * v] >= k) return kthZero(2 * v, tl, tm, k);
    return kthZero(2 * v + 1, tm + 1, tr, k - tree[2 * v]);
}

Здесь tree[v] — количество нулей на отрезке узла. Спуск идёт строго вниз, без возвратов: $O(\log n)$.

Так же ищется первый префикс с суммой не меньше $x$ — при условии, что элементы неотрицательны и префиксные суммы не убывают.

Спуск по монотонной величине

Второй вид: величина не аддитивна, зато монотонна по вложению. Максимум поддерева не меньше максимума любой его части, поэтому если максимум узла меньше $x$, внутри искать нечего.

int firstAtLeast(int v, int tl, int tr, int from, int x) {
    if (tr < from || tree[v] < x) return -1;
    if (tl == tr) return tl;
    int tm = (tl + tr) / 2;
    int got = firstAtLeast(2 * v, tl, tm, from, x);
    return got != -1 ? got : firstAtLeast(2 * v + 1, tm + 1, tr, from, x);
}

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

Спуск внутри отрезка

Оба примера ищут по всему массиву. Если вопрос про отрезок $[l, r]$, есть два способа.

Простой. Обычным запросом посчитать, сколько нулей на $[l, r]$; если меньше $k$ — ответа нет. Иначе посчитать количество нулей на префиксе до $l - 1$ и спуститься за $(k + \text{это число})$-м нулём по всему дереву. Два запроса и один спуск — те же логарифмы.

Быстрый. Написать спуск, который сам разбирается с границами: заходит в пересекающиеся узлы и вычитает по дороге. Быстрее по константе, но заметно легче ошибиться.

Начинайте с простого. Второй нужен, когда запросов миллионы.

Чем спуск отличается от двоичного поиска

Двоичный поиск задаёт дереву вопрос $\log n$ раз. Спуск использует то, что дерево само устроено как двоичный поиск, и обходится одним проходом.

Это общая мысль: если структура уже содержит нужное разбиение, искать поверх неё — значит делать работу дважды.