Дерево отрезков снизу, неявное дерево и корневая декомпозиция

Дерево отрезков снизу и неявное дерево

Дерево отрезков снизу

Дерево отрезков снизу — нерекурсивная реализация, где вершины нумеруются с 1, а дети вершины v — 2v и 2v + 1.

Построение

Найти минимальную степень двойки k, такую что 2^k >= n.
Размер массива дерева: 2^k + 1 (или 4n для простоты).

Листовые вершины

Элементу массива a[i] соответствует лист с номером 2^k + i. Родитель вершины u — u / 2 (целочисленное деление).

Операция обновления в точке (update)

void update(int i, int value) {
    i += (1 << k); // Переход к листу
    tree[i] = value;
    while (i > 1) {
        i /= 2; // Переход к родителю
        tree[i] = min(tree[2*i], tree[2*i + 1]); // Пересчёт
    }
}

Запрос на отрезке (get)

Работает на полуинтервале [l, r). Идея: сдвигать границы так, чтобы можно было перейти на слой выше.

int get(int l, int r) {
    l += (1 << k);
    r += (1 << k);
    int res = INF;
    while (l < r) {
        if (l % 2 == 1) res = min(res, tree[l++]);
        if (r % 2 == 1) res = min(res, tree[--r]);
        l /= 2; r /= 2;
    }
    return res;
}

Объяснение: Если l нечётное — его поддерево частично выходит за левую границу, вершину l нужно учесть сейчас. Аналогично для r.

Неявное дерево отрезков

Используется, когда размер массива велик (n до 10^18), но запросов относительно мало (q ~ 10^5).

Идея

Создаём вершины только при проходе по ним во время запросов. Всего вершин: O(q log n).

Реализация (на массивах, а не на указателях)

int ptr = 2; // Корень — вершина 1
int left[MAX], right[MAX], sum[MAX];

int new_node() {
    return ptr++;
}

void update(int v, int tl, int tr, int pos, int x) {
    if (tl == tr) {
        sum[v] = x;
        return;
    }
    int tm = (tl + tr) / 2;
    if (pos <= tm) {
        if (!left[v]) left[v] = new_node();
        update(left[v], tl, tm, pos, x);
    } else {
        if (!right[v]) right[v] = new_node();
        update(right[v], tm+1, tr, pos, x);
    }
    sum[v] = sum[left[v]] + sum[right[v]];
}

Рекомендации:

Используйте массивы, а не вектора, для скорости.
Выбирайте минимально достаточный тип данных (int32/int64).
Для задач, где важна лево-правая ориентация (например, максимальный подотрезок из единиц), накапливайте левую и правую части отдельно.

Массовые операции без пушей

В некоторых задачах можно избежать операций "проталкивания" (push), ускорив код.

Пример: прибавление на отрезке, минимум на отрезке

Храним в вершине значение add[v] — сколько нужно прибавить ко всему поддереву.

void update(int v, int tl, int tr, int l, int r, int x) {
    if (r <= tl || tr <= l) return;
    if (l <= tl && tr <= r) {
        add[v] += x;
        return;
    }
    int tm = (tl + tr) / 2;
    update(2*v, tl, tm, l, r, x);
    update(2*v+1, tm, tr, l, r, x);
    tree[v] = min(tree[2*v] + add[2*v], tree[2*v+1] + add[2*v+1]);
}

int get(int v, int tl, int tr, int l, int r, int acc = 0) {
    if (r <= tl || tr <= l) return INF;
    acc += add[v];
    if (l <= tl && tr <= r) return tree[v] + acc;
    int tm = (tl + tr) / 2;
    return min(get(2*v, tl, tm, l, r, acc),
               get(2*v+1, tm, tr, l, r, acc));
}

Инвариант: реальное значение в вершине = tree[v] + сумма add по всем предкам.

Дерево Фенвика (бинарное индексированное дерево)

Структура для операций прибавления в точке и суммы на префиксе за O(log n).

Основные операции

Пусть f(i) = i & -i (последний единичный бит).

Прибавление в точке i:

while (i <= n) {
    fenwick[i] += x;
    i += f(i);
}

Сумма на префиксе [1, i]:

int sum = 0;
while (i > 0) {
    sum += fenwick[i];
    i -= f(i);
}
return sum;

Спуск (поиск `k`-го порядка)

Поиск минимального k, такого что сумма на префиксе [1, k] >= x:

int k = 0;
for (int bit = (1 << logn); bit > 0; bit /= 2) {
    if (k + bit <= n && fenwick[k + bit] < x) {
        x -= fenwick[k + bit];
        k += bit;
    }
}
return k + 1; // Индексация с 1

Решение задач с помощью дерева отрезков

Количество различных чисел на отрезке (офлайн)

Будем обрабатывать массив слева направо (i от 1 до n).
В дереве отрезков будем хранить 1 в позиции i, если a[i] — самое правое вхождение этого числа на текущем префиксе, иначе 0.
При переходе i -> i+1:
- Если число a[i+1] встречалось ранее, ставим 0 в его предыдущей позиции.
- Ставим 1 в позиции i+1.
Ответ на запрос [l, r] с правым концом r — это сумма на отрезке [l, r] в дереве на момент обработки индекса r.

Mex на отрезке (офлайн)

Аналогично, храним в дереве отрезков индекс самого правого вхождения для каждого значения x.
При переходе i -> i+1 обновляем индекс для a[i+1].
Ответ на запрос [l, r] — минимальное x, для которого индекс последнего вхождения < l. Это делается спуском в дереве отрезков (поиск первого элемента с значением < l).

Прибавление арифметической прогрессии на отрезке

Запрос: прибавить на отрезке [l, r] значения a, a+d, a+2d, ....

Преобразуем прибавление к элементу a[k]: a[k] += (a - d*l) + d*k.
Заводим два дерева Фенвика/отрезков:
- Первое: прибавляет константу (a - d*l) на отрезке [l, r].
- Второе: прибавляет коэффициент d на отрезке [l, r].
Получение значения в точке i: ans = get1(i) + get2(i) * i.

Площадь объединения прямоугольников (сжатие координат + сканирующая прямая)

Сжимаем координаты y всех прямоугольников.
Идём сканирующей прямой по x. События: открытие и закрытие прямоугольника.
В дереве отрезков по y храним, скольким прямоугольникам покрыта каждая координата. Поддерживаем:
- add[v] — сколько прибавить ко всему поддереву.
- len[v] — длина покрытой части отрезка (если add[v] > 0, то len[v] = (r - l), иначе пересчёт из детей).
Площадь между событиями: (x2 - x1) * len[root].

Разбор конкретных задач

Задача 10: Минимальный путь с пропуском точки

Идея: При манхэттенском расстоянии всегда выгодно пропустить хотя бы одну точку.
Дельта: Для точки i вычисляется локальное изменение длины пути при её пропуске: delta[i] = dist(i-1, i) + dist(i, i+1) - dist(i-1, i+1).
Решение: Строится массив дельт. Ответ на запрос [L, R] – это суммарное расстояние между соседними точками на отрезке минус максимальная дельта на подотрезке (L, R).
Структуры данных: Нужно два дерева отрезков: на сумму (расстояния между соседями) и на максимум (дельты). При обновлении точки меняются только три соседние дельты.

Задача 11: Максимальная арифметическая прогрессия (шаг 1)

Сведение: Строится разностный массив diff[i] = (a[i] == a[i+1] - 1) ? 1 : 0. Задача сводится к поиску максимальной подпоследовательности из единиц на отрезке.
Дерево отрезков: В вершине хранится структура: максимальная длина цепочки единиц на отрезке, длина префикса из единиц, длина суффикса из единиц. Это позволяет быстро объединять отрезки.
Обобщение: Для прогрессии с произвольным шагом в структуре дополнительно хранятся первый/последний элемент отрезка и шаг прогрессии на префиксе/суффиксе.

Задача 12: НВП при условии |a[i] - a[i+1]| ≤ 1

Ключевое свойство (дискретная непрерывность): Если x стоит левее y и x < y, то между ними обязательно встретятся все числа x+1, x+2, ..., y-1 в порядке возрастания.
Следствие: Любая возрастающая подпоследовательность будет состоять из последовательных чисел. Её длина равна y - x + 1.
Сведение: Задача поиска длины НВП сводится к поиску максимальной разности a[j] - a[i] для j > i.
Решение: Дерево отрезков, хранящее в вершине минимум, максимум и максимальную разность на отрезке. Информация объединима.

Задача 13: Общий предок в двух деревьях

Условие предка: tin1[v] ≤ tin1[u] ≤ tout1[v] и tin2[v] ≤ tin2[u] ≤ tout2[v].
Геометрическая интерпретация (Решение 1):
- Каждой вершине v сопоставляется прямоугольник: [tin1[v], tout1[v]] x [tin2[v], tout2[v]].
- Каждой вершине u сопоставляется точка: (tin1[u], tin2[u]).
- Ответ – количество пар (прямоугольник v, точка u), где точка лежит в прямоугольнике. Решается сканирующей прямой и деревом отрезков.
DFS-решение (Решение 2):
- Запускается DFS по второму дереву.
- Поддерживается дерево отрезков по tin1. При входе в вершину v (она становится кандидатом в предки) на отрезке [tin1[v], tout1[v]] делается +1. При выходе – -1.
- Для вершины u ответ – это значение в дереве отрезков в точке tin1[u] (сколько активных вершин v являются её предками в первом дереве).

Задача 14: Минимальный сдвиг сенсоров

Формулировка: Найти минимальное d, такое что после прибавления d к координатам всех сенсоров, для каждой точки найдётся сенсор, который её доминирует по всем координатам (x, y, z).
Решение с бинпоиском:
1. Фиксируем d.
2. Для каждой точки (x, y, z) нужно проверить, есть ли сенсор (x', y', z') такой, что x' + d ≥ x, y' + d ≥ y, z' + d ≥ z.
3. Это трёхмерный запрос. Чтобы решить его эффективно:
  - Сортируем сенсоры и точки по убыванию x.
  - Используем сканирующую прямую: добавляем сенсоры в структуру.
  - Для добавленного сенсора (y', z') обновляем в дереве Фенвика (по координате y) максимальное значение z для этой y.
  - Для точки (y, z) запрос: максимум на суффиксе [y, ...] в этом дереве. Если этот максимум ≥ z, точка накрыта.
Решение без бинпоиска (опционально): Путём анализа формулы ответа и разбора случаев, какой из трёх аргументов в максимуме является наибольшим, задача сводится к нескольким более простым двумерным запросам.

Техники корневой декомпозиции

Разбиение на блоки (Задача A "Лунки")

Массив разбивается на блоки размера ~√n.
Для каждой позиции в блоке предподсчитывается, куда попадёшь, выпрыгнув из блока.
Обновление: Пересчёт одного блока за O(√n).
Запрос: Симуляция прыжков по блокам за O(√n).

Тяжёлые и лёгкие вершины (Задача C "Рёбра разных цветов")

Тяжёлая вершина: степень ≥ √m.
Лёгкая вершина: степень < √m.
Рёбра:
- Тяжёлый-Тяжёлый / Лёгкий-Лёгкий: таких рёбер из одной вершины O(√m), обновляются напрямую.
- Тяжёлый-Лёгкий: Для каждой тяжёлой вершины хранится массив cnt[color] – количество лёгких соседей данного цвета.
- Обновление цвета лёгкой вершины: Перебираем её тяжёлых соседей и обновляем их cnt.
- Обновление цвета тяжёлой вершины: По уже посчитанному cnt быстро пересчитываем вклад в ответ.

Корневая по запросам (Задача D "Арифметические прогрессии")

Запросы разбиваются на блоки размера ~√q.
После каждого блока за O(n + q) полностью пересчитывается состояние массива (используя технику двух разностных массивов для прогрессий).
Для координат, которые "пересекли" порог b[i] внутри блока, ответ ищется прямым моделированием запросов этого блока за O(√q).
Каждая координата обрабатывается так только один раз.

Оценки, основанные на корне

Количество различных значений ⌊n / d⌋ – O(√n).
Количество различных частот элементов в массиве – O(√n).
Количество делителей числа – O(√n).

Выводы

Дерево отрезков снизу — выбор для оптимизации по времени.
Неявное дерево — решение для больших диапазонов при малом числе запросов.
Дерево Фенвика — эффективная альтернатива для операций на префиксе.
Сканирующая прямая + дерево отрезков — мощный метод для геометрических и офлайн-задач.
Избегание пушей в массовых операциях может дать значительное ускорение.
Многие задачи на запросы к массивам и деревьям решаются комбинацией деревьев отрезков и сканирующей прямой.
Корневая декомпозиция – универсальный и мощный метод для задач, где сложно придумать точное логарифмическое решение. Ключевые идеи: разбиение на блоки, разделение объектов по "весу", амортизационные оценки.
Геометрическая интерпретация (перевод условия в задачу о точках и прямоугольниках) – мощный приём для задач на деревья и не только.
При работе со строками и множествами паттернов эффективно разделять их на "длинные" и "короткие", обрабатывая разными методами (прямой поиск и бор).

Дерево отрезков снизу, неявное дерево и корневая декомпозиция

Дерево отрезков снизу и неявное дерево