Занятие 2. Параллель A' — Структуры данных 1

1. Дерево отрезков «снизу» 0:00:00

Обычное рекурсивное дерево отрезков все знают. Альтернатива — итеративное («снизу», bottom-up), которое пишется быстрее и работает заметно быстрее по константе.

Идея. Берём $2^k \ge n$ (ближайшая степень двойки). Элементу $a_i$ соответствует лист с номером $2^k + i$, то есть номера вершин заполняют весь диапазон от $1$ (корень) до $2^{k+1}-1$ (последний лист). Поэтому под дерево нужен массив размера $2\cdot 2^k$ (а не $2^k+1$ — этого хватит только на сам слой листьев, без внутренних вершин). У вершины $v$ дети — $2v$ и $2v+1$, а родитель — $\lfloor v/2 \rfloor$. Корень — вершина 1.

Обновление в точке

Зная номер листа $2^k+i$, просто поднимаемся к родителю и пересчитываем, пока не дойдём до корня:

const int K = 1 << 20;  // 2^k >= n
int tree[2 * K];

void update(int i, int value) {
    i += K;                  // номер листа
    tree[i] = value;
    for (i /= 2; i > 0; i /= 2)
        tree[i] = tree[2*i] + tree[2*i+1];   // или min, max, ...
}

Запрос на полуинтервале $[l, r)$

Сдвигаем $l$ и $r$ на $K$ (в листья) и идём наверх. Пока $l < r$:

• если $l$ нечётно — добавляем tree[l] к ответу и делаем l++;
• если $r$ нечётно — делаем --r и добавляем tree[r];
• затем l /= 2, r /= 2.

int get(int l, int r) {   // полуинтервал [l, r)
    l += K; r += K;
    int res = 0;
    while (l < r) {
        if (l & 1) res += tree[l++];
        if (r & 1) res += tree[--r];
        l /= 2; r /= 2;
    }
    return res;
}

Смысл: если $l$ нечётно, его «предок» содержит лишний левый кусок, поэтому берём $l$ отдельно и сдвигаемся. Аналогично с правой границей. На каждом уровне полуинтервал сжимается в $\left\lfloor l/2 \right\rfloor, \left\lfloor r/2 \right\rfloor$.

2. Неявное дерево отрезков 0:20:00

Задача. Массив длины $10^9$ (все нули), операции: update(i, x) и get(l, r) — сумма на отрезке. $q \le 10^5$ запросов.

Обычное дерево займёт $4\cdot10^9$ — нельзя. Но вершин, которые нам реально нужны, мало: при обновлении создаётся $O(\log n)$ вершин.

Идея. Изначально в дереве только корень. Когда в запросе доходим до несуществующей вершины — создаём её на лету. Если вершины не существует, значит в её поддереве не было обновлений, и сумма там $0$.

const int MAXN = 20 * 100000;  // Q * log(n)
int ls[MAXN], rs[MAXN];        // дети (0 = не существует); вызывать update(1, 0, N, ...), get(1, 0, N, ...)
long long sum[MAXN];
int sz = 2;                     // 0 — «вершины нет» (sum[0] = 0), корень = 1

void update(int v, int l, int r, int i, long long x) {
    if (l == r - 1) { sum[v] = x; return; }
    int m = (l + r) / 2;
    if (i < m) {
        if (!ls[v]) ls[v] = sz++;      // создать левого сына
        update(ls[v], l, m, i, x);
    } else {
        if (!rs[v]) rs[v] = sz++;      // создать правого сына
        update(rs[v], m, r, i, x);
    }
    sum[v] = sum[ls[v]] + sum[rs[v]];  // (нет сына → sum = 0)
}

long long get(int v, int l, int r, int ql, int qr) {
    if (!v) return 0;                   // вершины нет → ноль
    if (ql <= l && r <= qr) return sum[v];
    int m = (l + r) / 2;
    long long res = 0;
    if (ql < m) res += get(ls[v], l, m, ql, qr);
    if (qr > m) res += get(rs[v], m, r, ql, qr);
    return res;
}

3. Массовые операции (ленивые) 0:37:00

Задача. add(l, r, x) — прибавить $x$ на отрезке; sum(l, r) — сумма на отрезке.

Храним в вершине два поля: sum[v] (сумма) и add[v] (ленивая добавка). Инвариант: реальное значение суммы вершины $=$ sum[v] + add[v]·(len). Функция push(v) проталкивает добавку детям.

void push(int v, int l, int r) {
    if (add[v] != 0) {
        add[2*v] += add[v];
        add[2*v+1] += add[v];
        add[v] = 0;
    }
}

void update(int v, int l, int r, int ql, int qr, long long x) {
    if (qr <= l || r <= ql) return;
    if (ql <= l && r <= qr) { add[v] += x; return; }
    push(v, l, r);
    int m = (l + r) / 2;
    update(2*v, l, m, ql, qr, x);
    update(2*v+1, m, r, ql, qr, x);
    sum[v] = sum[2*v] + add[2*v]*(m-l) + sum[2*v+1] + add[2*v+1]*(r-m);
}

4. Дерево Фенвика 0:44:00

Рассмотрим функцию $f(i) = i\ \&\ (-i)$ — это младший единичный бит числа $i$.

Почему так: $-x$ — это дополнение до двух (инвертировать биты и прибавить 1). Младшие нули $x$ при этом становятся единицами, а первый единичный бит сохраняется; побитовое «и» $x$ с $-x$ оставляет ровно этот бит.

Множество отрезков. Для каждого $i \in [1, n]$ определим отрезок $S_i = [i - f(i),\ i)$. Свойства:

1. $|S_i| = 2^k$ (степень двойки);
2. любые два $S_i$ либо вложены, либо не пересекаются.

Это позволяет построить дерево (для $n=16$ — красивая структура из отрезков-степеней двойки).

Операции

Прибавить в точке ($i$-й элемент): нужно обновить все отрезки, содержащие $i$. Родитель отрезка $i$ — это $i + f(i)$:

void add(int i, long long x) {          // 1-индексация
    for (; i <= n; i += i & (-i)) t[i] += x;
}

Сумма на префиксе $[1, i]$: нужно взять вложенные отрезки, идя «влево»:

long long pref(int i) {
    long long s = 0;
    for (; i > 0; i -= i & (-i)) s += t[i];
    return s;
}

Обе операции — $O(\log n)$, причём по факту Фенвик быстрее даже дерева отрезков снизу (всего пара операций на итерацию).

Спуск по Фенвику 1:05:00

Задача: найти минимальное $k$, такое что сумма на префиксе $[1,k]$ хотя бы $x$. Идём по степеням двойки от $\log n$ до $0$: если можем добавить блок размера $2^i$ и сумма всё ещё $< x$ — добавляем.

int k = 0;
for (int i = LOG; i >= 0; --i) {
    if (k + (1 << i) <= n && x > t[k + (1 << i)]) {
        k += (1 << i);
        x -= t[k];
    }
}
// ответ: k + 1

Это жадно по битам от старших к младшим — тот же приём, что подъём/спуск по двоичному дереву.

5. Сжатие координат 1:41:00

Если координаты большие, а запросов мало — выписываем все интересующие координаты, сортируем, убираем дубликаты и заменяем значение на его индекс через lower_bound.

vector<long long> xs;
for (запрос) xs.push_back(l), xs.push_back(r);   // все координаты
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());
// замена координаты v:
int id = lower_bound(xs.begin(), xs.end(), v) - xs.begin();

6. Базовые применения (разностный массив, прогрессии, минимум) 1:18:00

Задача 1. Прибавление на отрезке, финальный массив (оффлайн)

Разностный массив $d_i = a_i - a_{i-1}$. Операция «прибавить $x$ на $[l,r]$» превращается в два изменения: $d_l \mathrel{+}= x$, $d_{r+1} \mathrel{-}= x$. В конце восстанавливаем $a$ префиксными суммами $d$. Суммарно $O(n + q)$.

Задача 2. Арифметическая прогрессия на отрезке + значение в точке

Хотим: к $a_l$ прибавить $A$, к $a_{l+1}$ — $A+d$, …, к $a_r$ — $A+d(r-l)$. Для элемента $k$ прибавка равна $A + d\cdot k - d\cdot l$. Раскроем на две независимые части:

• Свободный член $A - d\cdot l$ — обычное прибавление константы на отрезке.
• Линейный коэффициент $d$ — ещё одно прибавление константы на отрезке (в другом массиве).

Заводим два Фенвика (или два разностных массива): один для свободных членов, второй для коэффициентов при $k$. Ответ в точке: $v_1(k) + v_2(k)\cdot k$.

Задача 3. Минимум на отрезке + прибавление

Дерево отрезков с ленивой добавкой (см. §3, вариант «без пушей»).

Задача 5–6. Непересекающиеся отрезки (жадность и ДП)

Максимум непересекающихся отрезков — жадность: сортируем по правой границе, берём отрезок, если он не пересекается с последним взятым. С весами — ДП: $dp[i] = \max(dp[i-1],\ \max_{j: r_j = i} (w_j + dp[l_j-1]))$; максимум на префиксе поддерживается деревом отрезков.

7. Сканлайн: количество различных и MEX 2:05:00

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

Для каждого запроса $[l,r]$ нужно посчитать число различных значений. Оффлайн: идём по массиву слева направо, поддерживая для каждого значения позицию его самого правого вхождения на текущем префиксе.

Тогда количество различных на $[l,r]$ (где $r$ — текущая позиция) — это сумма на отрезке $[l, r]$. Каждое значение даёт ровно одну единичку внутри отрезка, если оно там встречается.

MEX на отрезке

Те же идеи, но теперь дерево хранит последнее вхождение каждого значения. MEX на $[l,r]$ — минимальное $x$, у которого последнее вхождение $< l$. Строим дерево отрезков на минимум по значениям и делаем спуск в первый лист с минимумом $< l$.

// дерево на минимум; ищем первый x с last[x] < l
int descend(int v, int tl, int tr, int l) {
    if (tl + 1 == tr) return tl;
    int m = (tl + tr) / 2;
    if (tree[2*v] < l) return descend(2*v, tl, m, l);
    else                 return descend(2*v+1, m, tr, l);
}

8. Спуск по дереву: первое число $\ge k$ 2:27:00

Задача: найти первое число на префиксе (или подотрезке), большее либо равное $k$.

Храним в дереве отрезков максимум. При спуске смотрим: если максимум левого сына $\ge k$ — идём влево, иначе вправо. Если максимум текущей вершины $< k$ — останавливаемся (в этом поддереве искомого нет).

9. Задачи на «составную» информацию в вершине 2:37:00

Многие задачи на дерево отрезков сводятся к тому, чтобы придумать в каждой вершине такую информацию, которую можно корректно объединять.

Задача 10. Пропуск точки на пути 2:37:00

Дан массив точек $(x_i, y_i)$; обновления на отрезке; запрос: минимальная длина пути по точкам (манхэттенское расстояние между соседними), если можно пропустить одну точку.

Для каждой точки $i$ определим дельту — насколько уменьшится путь, если её пропустить:

Дальше нужны два дерева: одно на сумму расстояний между соседями (исходная длина пути), второе на максимум дельт. Ответ = сумма − максимум дельты. Обновление точки меняет лишь несколько соседних элементов этих массивов.

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

Запрос: максимальная по длине подпоследовательность подряд идущих элементов отрезка, являющаяся арифметической прогрессией с шагом 1; плюс прибавление на отрезке.

Ключевой «рефлекс»: переход к разностному массиву. Прогрессия с шагом 1 — это подряд идущие единицы в разностном массиве. В каждой вершине дерева храним: длину префикса из единиц, длину суффикса из единиц, ответ (максимум подряд единиц) и длину отрезка. При слиянии двух кусков ответ = max(левый ответ, правый ответ, левый суффикс + правый префикс).

Задача 12. НВП при $|a_{i+1} - a_i| \le 1$ 2:54:00

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

Дискретная непрерывность. Если $x$ стоит левее $y$ и $x < y$, то на пути между ними встретятся все значения $x, x+1, \dots, y-1, y$ (в нужном порядке) — потому что шаг между соседями $\le 1$.

Значит, в вершине дерева храним минимум, максимум и ответ; при слиянии ответ обновляется как разность максимума правого куска и минимума левого.

10. Деревья, точки/сенсоры и прочее 3:05:00

Задача 13. Пары «предок–потомок» в двух деревьях 3:05:00

Даны два дерева на одних и тех же вершинах; нужно посчитать число пар $(v,u)$, где $v$ — предок $u$ в обоих деревьях.

Запустим DFS по первому дереву и вычислим времена входа/выхода: $v$ — предок $u$ $\Leftrightarrow$ $tin_1[v] \le tin_1[u] \le tout_1[v]$. То же для второго дерева. Получаем $n$ «прямоугольников» (по $v$) и $n$ «точек» (по $u$), и нужно посчитать количество пар «точка лежит в прямоугольнике».

• Решение 1 (сканлайн). События по координате $x$: точка → добавить на позиции $y$; открытие/закрытие прямоугольника → спросить сумму на отрезке $y$.
• Решение 2 (DFS по второму дереву). Идём DFS по второму дереву; в дереве отрезков поддерживаем для каждой активной (на пути от корня) вершины $v$ добавку +1 на $[tin_1[v], tout_1[v]]$. Тогда число подходящих $v$ для текущего $u$ — это сумма в позиции $tin_1[u]$. При заходе в вершину добавляем, при выходе — откатываем (вычитаем).

Задача 14. Точки и сенсоры 3:22:00

Даны точки $(x_i, y_i, z_i)$ и сенсоры $(x'_j, y'_j, z'_j)$. Найти минимальное $D$, при котором, сдвинув все сенсоры на $+D$ по каждой координате, для каждой точки найдётся сенсор, превосходящий её покоординатно.

Пункты 1–2: бинпоиск по $D$. Для фиксированного $D$ нужно проверить, что для каждой точки есть сенсор $g$ с $x'_g + D \ge x_i$, $y'_g + D \ge y_i$, $z'_g + D \ge z_i$. Это 3D-запрос, но решается двумя сканлайнами:

• Сканлайн по $x$ (в порядке убывания): добавляем сенсоры с подходящим $x$.
• По координате $y$ (сжатой) строим дерево/Фенвик, где в позиции $y$ хранится максимум $z$ добавленных сенсоров. Проверка — максимум на суффиксе $y \ge y_i$.

Пункт 3 (без бинпоиска). Записываем ответ как $\max_i \min_g \max(x_i - x'_g,\ y_i - y'_g,\ z_i - z'_g)$. Фиксируем, какая из трёх компонент реализует внутренний максимум, и для каждого случая получаем задачу поиска максимума/минимума по парам с условием, решаемую сканлайном. Это избавление от бинпоиска через «max-min» формулу.

11. Разбор контеста (корневая декомпозиция) 3:41:00

Контест был на корневую декомпозицию (связь с прошлым занятием).

Разбор D: применяем корневую по запросам. После каждого блока восстанавливаем массив за $O(n+q)$ (разностный массив + префиксные суммы). Для каждой координаты, «переполнившейся» внутри блока, честно проходим по запросам блока. Ключевой факт: $q$ запросов прогрессий применяются за $O(n+q)$ через разностный массив разностного массива.