0:00 Параллель X — самая продвинутая: цель — подготовить к соревнованиям уровня студенческих олимпиад и раундов на Codeforces и CodeChef. Часть тем выходит за рамки школьных олимпиад.
6:00 Тема занятия — применение дерева отрезков. Начинаем с повторения классической задачи.
6:30 Условие. Дан массив $a_1,\dots,a_n$ и много запросов $(l,r,x)$: сколько чисел $a_i$ с $l\le i\le r$ не превосходят $x$? Нужно ответить на каждый запрос онлайн.
8:00 Merge sort tree. Строим дерево отрезков по индексам, в каждой вершине храним отсортированный массив значений её отрезка (он получается слиянием массивов детей). Запрос раскладывается на $O(\log n)$ вершин, в каждой — бинпоиск по её массиву: $O(\log^2 n)$ на запрос, $O(n\log n)$ времени и памяти на построение.
11:47 Бинпоиски в вершинах можно ускорить. Для каждой позиции $i$ массива вершины запомним два числа: индекс первого элемента, строго большего $y$, в левом сыне и в правом сыне (где $y=a_i$ — значение этой позиции). Эти индексы получаются бесплатно при слиянии: это ровно те два указателя, которыми мы идём по массивам детей. Тогда достаточно сделать один бинпоиск в корне, а в сыновьях позиция находится за $O(1)$ по сохранённым указателям: запрос работает за $O(\log n)$ вместо $O(\log^2 n)$. Эта техника называется частичное (дробное) каскадирование. 14:24
16:50 Если запросы известны заранее (офлайн), задачу можно решить проще. Запрос сводится к разности двух «префиксных» запросов $(r,x)$ и $(l-1,x)$, где нужно найти число $i\le r$ с $a_i\le x$. Идём «сканирующей прямой» по индексу, поддерживая массив длины $V$ (число различных значений) нулей и единиц, где в позиции $v$ стоит единица, если значение $v$ уже встречалось; для суммы на отрезке значений годится дерево Фенвика. Геометрически: числа — точки $(i,a_i)$ на плоскости, запрос — число точек в прямоугольнике. Прямую можно двигать по любой из осей: иногда полезно по значениям, иногда по индексам. 20:17
20:17 Оба решения устроены одинаково: структура данных, в которой во время сканирования делаются $n$ обновлений, а запросы приходят «в разные моменты» этого процесса. Чтобы отвечать на них онлайн, сохраним все исторические версии дерева — это персистентное дерево отрезков. Обновление создаёт только $O(\log n)$ новых вершин (путь от корня до изменённого листа — остальные ссылки указывают на старые вершины). Версия $v_i$ — состояние после первых $i$ вставок.
Запрос «сколько $a_j\le x$ на $[l,r]$» — разность двух версий: $\text{cnt}(v_{r},\le x)-\text{cnt}(v_{l-1},\le x)$ (индексация с 1). Итого: $O(n\log n)$ времени и памяти на построение и $O(\log n)$ на запрос — те же асимптотики, что и у каскадирования. 24:22
24:22 Любопытный факт: merge sort tree с каскадированием — это почти то же самое персистентное дерево. Указатели на сыновей в нём играют роль ссылок на «актуальных детей вершины» после очередной вставки; префикс чисел, не больших $x$, в вершине соответствует версии дерева на этот момент.
// Статический пул вершин; ссылки — индексы (так быстрее, чем new и указатели)
const int MAXN = 4000000;
int Lc[MAXN], Rc[MAXN], Cnt[MAXN], tot = 0; // сыновья и счётчик
int add(int prev, int lo, int hi, int pos) { // новая версия: +1 в позиции pos, [lo,hi)
int cur = ++tot; Lc[cur] = Lc[prev]; Rc[cur] = Rc[prev]; Cnt[cur] = Cnt[prev] + 1;
if (hi - lo > 1) {
int mid = (lo + hi) / 2;
if (pos < mid) Lc[cur] = add(Lc[prev], lo, mid, pos); // копируем только путь вниз
else Rc[cur] = add(Rc[prev], mid, hi, pos);
}
return cur;
}
int countLE(int a, int b, int lo, int hi, int x) { // сколько <= x в разности версий b и a
if (x < lo) return 0;
if (x >= hi - 1) return Cnt[b] - Cnt[a];
int mid = (lo + hi) / 2;
return countLE(Lc[a], Lc[b], lo, mid, x) + countLE(Rc[a], Rc[b], mid, hi, x);
}
// ver[0] = 0 (пустое дерево), ver[i+1] = add(ver[i], 0, V, a[i]);
// ответ на [l, r] (с нуля): countLE(ver[l], ver[r+1], 0, V, x)27:44 Условие. Дан массив и запросы $(l,r)$: сколько различных значений на $[l,r]$ (размер множества $\{a_l,\dots,a_r\}$)? Тупое решение — проход по отрезку с массивом счётчиков: $O(n)$ на запрос.
30:00 Сортируем запросы по правой границе $r$ и двигаем $r$ вправо. Для каждого значения нас интересует только его последнее вхождение: пусть в позиции последнего вхождения каждого значения стоит 1, на более ранних вхождениях — 0. Тогда число различных значений на $[l,r]$ — сумма единиц на $[l,r]$. При сдвиге $r$ в позицию $r$ ставим 1, а на прежнее вхождение этого значения — 0: два точечных обновления и запрос суммы — дерево Фенвика или дерево отрезков, $O((n+q)\log n)$.
30:30 Для каждой позиции $i$ вычислим $\text{prev}_i$ — индекс предыдущего вхождения того же значения (или $-1$). Значение $a_i$ учитывается на $[l,r]$ ровно тогда, когда $i$ — его первое вхождение на отрезке, то есть $\text{prev}_i<l$. Тогда:
Это уже знакомая задача «сколько чисел на отрезке не больше $x$» для массива $\text{prev}$ и $x=l-1$ — решаем персистентным деревом. Онлайн, $O(n\log n)$ памяти, $O(\log n)$ на запрос. 37:13 (Лектор показывает и вариант «сдвигать по префиксу»: тогда запрос превращается в запрос на отрезке в одном дереве, без вычитания версий; константа получается лучше, но это скорее приём оптимизации.)
set на 9000 случайных запросов.44:54 Условие. Запросы $(l,r)$: найти $\operatorname{mex}$ — минимальное неотрицательное число, которого нет среди $a_l,\dots,a_r$. Для этой стандартной задачи часто вспоминают корневую декомпозицию (хранить в блоках счётчики и искать первую «дыру» по блокам за $O(\sqrt n)$), и забывают, что она решается за $O(\log n)$.
45:00 Идея (офлайн). Числа, которые больше $n$, на mex не влияют — их игнорируем. Идём сканирующей прямой по правой границе $r$ и поддерживаем массив $\text{last}[x]$ — индекс последнего вхождения числа $x$ в префиксе $[0..r]$ (или $-1$). Число $x$ присутствует на $[l,r]$ тогда и только тогда, когда $\text{last}[x]\ge l$. Значит,
48:26 Для этого строим дерево отрезков на $\min$ над массивом $\text{last}$ и спускаемся: если минимум в левом сыне $<l$, ответ слева, иначе справа. Обновление — одна точка (при чтении $a_r$ ставим $\text{last}[a_r]=r$). Всё работает за $O((n+q)\log n)$. 49:00
struct MinTree { // дерево на min по last[0..n]
int n; vector<int> t;
MinTree(int n) : n(n), t(4 * n, -1) {}
void upd(int v, int l, int r, int p, int x) { // last[p] = x
if (r - l == 1) { t[v] = x; return; }
int m = (l + r) / 2;
if (p < m) upd(2 * v, l, m, p, x); else upd(2 * v + 1, m, r, p, x);
t[v] = min(t[2 * v], t[2 * v + 1]);
}
int firstLess(int v, int l, int r, int bound) { // минимальный x с last[x] < bound
if (r - l == 1) return l;
int m = (l + r) / 2;
return t[2 * v] < bound ? firstLess(2 * v, l, m, bound) : firstLess(2 * v + 1, m, r, bound);
}
};
// запросы отсортированы по r; при r: if (a[r] <= n) mt.upd(1, 0, n + 1, a[r], r);
// затем для запросов с этим r: ans = mt.firstLess(1, 0, n + 1, l);50:00 Онлайн. Если добавить персистентность, получится онлайн-решение за $O(\log n)$ на запрос. «Персистентность + спуск» — частая комбинация, которая решает нестандартные запросы онлайн за логарифм без лишних множителей.
set на 9000 случайных запросов (значения 0–7, $n\le12$).50:30 Условие. Запросы $(l,r,k)$: найти $k$-е по величине число на $[l,r]$ (например, медиану).
1:00:51 Решение 1 (бинпоиск + персистентность). Бинпоиск по ответу: проверка «на $[l,r]$ хотя бы $k$ чисел $\le x$» — это уже решённая задача (подсчёт $\le x$ на отрезке) за $O(\log n)$. Итого $O(\log^2 n)$ на запрос.
1:00:51 Решение 2 (спуск по разности версий). Внешний бинпоиск лишний. В обоих запросах к версиям $r$ и $l-1$ мы делаем одинаковые действия — «сумма на префиксе значений до $x$». Поэтому мысленно возьмём дерево-разность: в каждой вершине — разность счётчиков двух версий (структура у деревьев одинаковая, поэтому вершины соответствуют одним и тем же отрезкам значений). Это дерево отрезков по значениям для массива подсчёта чисел внутри $[l,r]$. В нём нужно найти $k$-ю единицу — обычный спуск: если в левом сыне $c\ge k$ чисел, идём влево, иначе идём вправо с $k-c$.
int kth(int a, int b, int lo, int hi, int k) { // a = версия l-1, b = версия r
if (hi - lo == 1) return lo; // лист — значение
int mid = (lo + hi) / 2, c = Cnt[Lc[b]] - Cnt[Lc[a]]; // сколько чисел в левой половине значений
return k <= c ? kth(Lc[a], Lc[b], lo, mid, k)
: kth(Rc[a], Rc[b], mid, hi, k - c);
}
// значения предварительно сжаты до 0..V-1; ответ — kth(ver[l], ver[r + 1], 0, V, k)1:05:00 Условие. Дано дерево, на рёбрах записаны числа. Запрос $(u,v,k)$: найти $k$-е по величине число среди рёбер пути $u\to v$.
1:05:30 Для каждой вершины храним персистентное дерево по значениям, содержащее числа на пути от корня до неё (версия вершины = версия родителя плюс вставка веса ребра к родителю). Для пути $u\to v$ с наименьшим общим предком $w=\operatorname{lca}(u,v)$ множество рёбер — это «путь от корня до $u$» плюс «путь от корня до $v$» минус дважды «путь от корня до $w$». Поэтому счётчик каждого значения на пути равен
1:08:00 Это более сложная линейная комбинация трёх деревьев, но она остаётся корректной. Спуск идёт параллельно по трём деревьям: в каждой вершине считаем $c=(\text{левый сын }u)+(\text{левый сын }v)-2(\text{левый сын }w)$ и выбираем направление. Время запроса — $O(\log n)$ на спуск плюс $\operatorname{lca}$.
1:15:00 Бывает, что запросов намного больше, чем длина массива. Обычная sparse table отвечает на запрос за $O(1)$, но работает лишь для идемпотентных операций ($\min$, $\max$, $\gcd$): перекрывающиеся половины не мешают. Для суммы или более сложных (неидемпотентных) операций надо разбивать отрезок на непересекающиеся части. Структура, делающая это за $O(1)$ запросов, называется disjoint sparse table.
1:16:40 Делим массив пополам по границе $m$. Для левой половины считаем значения на всех суффиксах (отрезки $[i,m-1]$), для правой — на всех префиксах ($[m,j]$). Затем рекурсивно то же для каждой половины. Любой отрезок $[l,r]$, пересекающий границу $m$, равен «суффикс левой половины» + «префикс правой половины» — всего два готовых значения. Если отрезок целиком в одной половине, спускаемся в неё.
1:19:30 Сложность. На каждом уровне рекурсии храним $n$ значений, уровней $\log n$: память $O(n\log n)$. Если значение на очередном суффиксе/префиксе получается из предыдущего добавлением одного элемента за $T$ — построение $O(nT\log n)$. Запрос: спуск по дереву за $O(\log n)$ или за $O(1)$: если длина массива — степень двойки и позиции нумеруются с нуля, то отрезок $[l,r]$ «разделяется» на уровне, равном номеру старшего бита числа $l\oplus r$ — по нему сразу находим нужный уровень и берём два значения. Итого запрос $O(T_\text{merge})$, где $T_\text{merge}$ — стоимость объединения двух частей.
struct DST { // сумма; для другой операции меняется только "+"
int n, LOG; vector<vector<long long>> t; vector<long long> base;
DST(const vector<long long>& a) {
n = 1; LOG = 0; while (n < (int)a.size()) n <<= 1, LOG++;
base.assign(n, 0); copy(a.begin(), a.end(), base.begin());
t.assign(max(LOG, 1), vector<long long>(n));
for (int h = 0; h < LOG; h++) {
int half = 1 << h;
for (int mid = half; mid < n; mid += 2 * half) { // граница между блоками
t[h][mid - 1] = base[mid - 1];
for (int i = mid - 2; i >= mid - half; i--) t[h][i] = t[h][i + 1] + base[i]; // суффиксы левой
t[h][mid] = base[mid];
for (int i = mid + 1; i < mid + half; i++) t[h][i] = t[h][i - 1] + base[i]; // префиксы правой
}
}
}
long long query(int l, int r) { // сумма на [l, r], 0-индексация
if (l == r) return base[l];
int h = 31 - __builtin_clz(l ^ r); // уровень, на котором l и r разделяются
return t[h][l] + t[h][r];
}
};1:26:13 Условие. Даны массив и число $m$; запросы $(l,r)$: найти число подпоследовательностей (не обязательно подряд идущих) элементов отрезка с суммой, кратной $m$, по модулю простого числа.
1:26:13 Для отрезка храним массив $f[0..m-1]$, где $f[s]$ — число подпоследовательностей с суммой $\equiv s\pmod m$ (с учётом пустой). Слияние двух отрезков — «циклическая свёртка» $O(m^2)$: $f[s]=\sum_{i+j\equiv s}f_1[i]f_2[j]$. Тогда обычное дерево отрезков работает за $O(m^2\log n)$ на запрос. Но в disjoint sparse table:
Итого $O(nm\log n+qm)$ — заметно лучше, когда $q\gg n$. Общая мысль: не любое слияние отрезков дорого — слияние «отрезка с одним числом» или «двух готовых половинок для одного значения» может быть существенно проще. 1:36:51
1:36:51 Задача. Минимум на отрезке и прибавление на отрезке. Обычно прибавление делают с «ленивыми» пометками и push при спуске. Если операции перестановочны (сложение), push можно вообще не делать.
1:36:51 В каждой вершине $v$ храним два числа: $\text{mn}_v$ — минимум на её поддереве с учётом $\text{mod}_v$ и всех модификаторов ниже, и $\text{mod}_v$ — «прибавлено ко всему отрезку вершины $v$» (но не учтено в предках). Инвариант: $\text{mn}_v=\min(\text{mn}_l,\text{mn}_r)+\text{mod}_v$.
get(v) возвращает минимум на пересечении запроса с поддеревом $v$ без модификаторов предков: если вершина целиком внутри запроса — $\text{mn}_v$, иначе $\min(\text{get}(l),\text{get}(r))+\text{mod}_v$. Модификаторы предков добавляются по пути вверх рекурсии.void add(int v, int l, int r, int ql, int qr, long long x) { // [l, r), [ql, qr)
if (qr <= l || r <= ql) return;
if (ql <= l && r <= qr) { mn[v] += x; mod[v] += x; return; }
int m = (l + r) / 2;
add(2 * v, l, m, ql, qr, x); add(2 * v + 1, m, r, ql, qr, x);
mn[v] = min(mn[2 * v], mn[2 * v + 1]) + mod[v]; // модификатор остаётся здесь
}
long long get(int v, int l, int r, int ql, int qr) { // без модификаторов предков
if (qr <= l || r <= ql) return INF;
if (ql <= l && r <= qr) return mn[v];
int m = (l + r) / 2;
return min(get(2 * v, l, m, ql, qr), get(2 * v + 1, m, r, ql, qr)) + mod[v];
}1:42:00 Когда push необходим: если операции не коммутируют (например, присваивание на отрезке) — там важен порядок применения. Если же порядок неважен, обходиться без push часто удобно, а для персистентных деревьев это особенно ценно (push создавал бы новые вершины при каждом спуске).
1:43:00 Итоги: персистентность — основной инструмент «онлайн вместо офлайна»; спуск по дереву решает задачи вида «найти $k$-е / первое», которые обычно решают бинпоиском; disjoint sparse table нужна, когда запросов много, а операция неидемпотентна. Позже выдают задание на следующий тур.