Лекция 2. Дерево отрезков

Запросы на массиве. Полуинтервал $[\ell;r)$. sum(l, r) — сумма на отрезке, префиксные суммы.

Дерево отрезков sum(l, r) и set(i, x), идея, реализация на указателях.

Что можно вместо sum? Достаточное условие — ассоциативность операции и наличие нуля. Определение моноида. Полугруппа, как получить из полугруппы моноид. Дерево отрезков работает на полугруппе. Примеры:

а) абелева группа ($+$, $\times_{\mathbb R\setminus{0}}$, $\oplus$, $+_{\mathbb R[x]}$, сложение и умножение можно по простому модулю, а иногда и не простому);

б) абелев моноид ($+_{\mathbb N_0}$, $\times$, $\times_{\mathbb R[x]}$, $\wedge$, $\vee$, $\gcd$, $\mathrm{lcm}$);

в) абелева полугруппа (необратимые элементы абелевых моноидов: 1) явно выкинуть единицу: $+_{\mathbb N}$, $\wedge_{\mathbb N_0}$, $\vee_{\mathbb N}$; 2) идеал в любом кольце: чётные целые числа по умножению, многочлены, кратные какому-то многочлену, многочлены с чётным свободным членом);

г) группа (перестановки $S_n$, биективные преобразования множества, обратимые матрицы/линейные отображения $\mathrm{GL}(n, \mathbb R)$);

д) моноид (квадратные матрицы $\mathcal M_{n \times n}$, верхнетреугольные матрицы, все преобразования на множестве);

е) полугруппа (необратимые элементы моноидов: обратимые матрицы, небиективные отображения; отображение $a\cdot b=a$).

Массовые операции изменения. Две операции sum(l, r) и update(l, r, x), первая находит $\bigoplus\limits_{i=\ell}^{r-1}x_i$, вторая применяет $x_i:=x_i\otimes x$ для всех $i\in[\ell;r)$. Удобный случай: дистрибутивность $\oplus$ и $\otimes$: $(a\oplus b)\otimes c=(a\otimes c)\oplus(b\otimes c)$. Примеры: $(\min, P_2)$, $(\min, +)$, $(+, \cdot)$ (здесь $P_2(x, y)=y$).

1) Почему нельзя сделать так, как в прошлом дереве отрезков?

2) Как понять изменение в вершине без вычисления изменений в детях? Дистрибутивность помогает.

3) Идея lazy propagation.

4) От некоторых условий можно избавляться. Можно избавиться от дистрибутивности, заменив её тем, что $\bigoplus\limits_{i=\mathrm{node}{.}\ell}^{\mathrm{node}{.}r-1}{x_i\otimes x}$ можно выразить через $\bigoplus\limits_{i=\mathrm{node}{.}\ell}^{\mathrm{node}{.}r-1}{x_i}$, $\mathrm{node}{.}\ell$, $\mathrm{node}{.}r$ и $x$.

5) Мы пользуемся декомпозируемостью $f(a, b, c)=g(g(a, b), c)$. От неё тоже можно избавиться.

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

Персистентное дерево отрезков.