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

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


2. Деревья, fractional-cascading, ромбики
1. ДО сортированных массивов и fractional-cascading
2. Параллельные бинпоиски − для каждой точки на плоскости найти ближайшую по L₁, L_inf
3. Задача про ∑ max (x_i - x^*, y_i - 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)