СНМ

1. Храним color[i] и list[color], size[color]
2. Перекрашиваем список меньшей длины. Суммарная время работы join-ов = NlogN.
1. Обобщение этой идеи: Add → Merge
3. Лес
1. Меньшее к большему
2. Сжатие путей
3. Док-во оценки O(log^*N)

Hash-Таблицы

1. Открытая адресация [Add, Find]
2. Списки [Add, Del, Find]
3. Удвоение при переполнении
4. Оценка вероятности того, что длина списка будет хотя бы K.

Сбалансированные деревья

1. Несбаллансированное дерево
2. Малые вращения, большие вращения
3. Splay-дерево
4. Необычное дерево (перебаллансировка когда size[v] = 2^k)
5. Сбаллансированное дерево умеет все, что умеет дерево отрезков.

Двумерные Структуры данных - часть 1

1. Дерево отрезков + ScanLine = решение задачи сумма в прямоугольнике в Offline
2. Дерево отрезков, в каждой вершине отсортированный массив = решение задачи сколько чисел на отрезке [i..j] имеет значение от [x..y]
3. Прерыдущая задача эквивалентна "числу точек в прямоугольнике"
4. Дерево отрезков декартовых деревьев

Persistent

1. Persistent Tree
2. Массив = Дерево отрезков
3. Весь мир = массивы
4. Garbage Collector = подсчет ссылок

Задачи на пройденные структуры данных

1. Структура, умеющая делать Add, Del, Find и ListAll
2. Задача про максимальное ребро за O(E)
3. структура, которая умеет делать Add, Find, Del, GetRandomItem

Бор и Сжатый бор

1. Бор строк. Суффиксное дерево строк. Определения.
2. Хранения бора. Массив, список, хэш-таблица.
3. Решение задачи про подстроки за O(N²)
4. Решение задачи про поиск словарных слов в тексте за O(E*Len).
5. Сжатый бор. Сжатое суффиксное дерево. Память = O(NE), где N - число строк, E - размер алфавита.
6. У сжатого бора необычная малая константа. Решение задачи про подстроки для Len = 20 000.