Лекция 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)\). От неё тоже можно избавиться.

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

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