## ЛКШ 2018, 10-й день, Структуры данных (Даня Николенко)

1. Мо

1. Классика на примере "число различных на отрезке" или "число инверсий на отрезке"
2. 3D-версия
3. Версия на дереве на примере "сумма на пути в дереве"
4. Избавление от лога

2. Деревья, fractional-cascading, ромбики

1. ДО сортированных массивов и fractional-cascading
2. Параллельные бинпоиски − для каждой точки на плоскости найти ближайшую по L1, Linf
3. Задача про ∑ max (xi - x*, yi - y*) → min
4. Fractional cascading для параллельных бинпоисков
5. Дерево Ли-Чао (dynamic convex hull)

3. Ещё несколько структур данных

1. RMQ-Offline
2. Disjoint Sparse Table (аналог на массиве)
3. Centroid Decomposition: RMQ за O(1) на дереве
4. HLD: считать и от пути, и от отрезка

4. Доказательство Splay-Tree (и версии с Link-Cut)