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. Квадратный корень по модулю