1. Двоичная куча

2. Левосторонняя куча

3. Биномиальная куча

4. Фибоначчиева куча

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

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

3. Что можно вместо 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$).

4. Массовые операции изменения. Две операции 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)$. От неё тоже можно избавиться.

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

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

1. Дерево поиска. Инвариант АВЛ-дерева

2. Splay-дерево, операция splay, потенциал

3. Операции split и merge в splay-дереве

4. Дерево по неявному ключу — концепция, реализация при помощи splay-дерева

1. Задача LCA поиска нижайшего общего предка двух вершин в подвешенном дереве. Решение с $\mathcal O(n\log n)$ препроцессинга и памяти, $\mathcal O(1)$ на запрос: двоичные подъёмы.

2. Задача RMQ поиска минимума на подотрезках массива. Сведение LCA к RMQ за $\mathcal O(n)$: эйлеров обход.

3. LCA и RMQ с $\mathcal O(n)$ препроцессинга и памяти, $\mathcal O(\log n)$ на запрос: дерево отрезков.

4. LCA и RMQ с $\mathcal O(n\log n)$ препроцессинга и памяти, $\mathcal O(1)$ на запрос: разреженная таблица.

5. LCA и частный случай RMQ с $\mathcal O(n)$ препроцессинга и памяти, $\mathcal O(1)$ на запрос: алгоритм Фараха-Колтона, Бендера.

Лекция

1. О факторкольце и факторполе по натуральному и простому модулю

2. Полная и приведённая система вычетов

3. Теорема Эйлера, малая теорема Ферма

4. Обратный по модулю при известном $\varphi(m)$. $\varphi(p)=p-1$

5. Алгоритм Евклида. Расширенный алгоритм Евклида, линейное представление НОДа, обратный по произвольному модулю

6. Решето Эратосфена, факторизующее решето Эратосфена

7. Тест простоты Ферма. Числа Кармайкла

8. Тест Миллера-Рабина

9. $\rho$-алгоритм Полларда для факторизации

10. $p-1$-алгоритм Полларда для факторизации

11. Первообразный корень по модулю

12. Дискретный логарифм по модулю

13. Квадратный корень по модулю