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

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

<br>
# Деревья, fractional-cascading, ромбики
## ДО сортированных массивов и fractional-cascading
## Параллельные бинпоиски -- для каждой точки на плоскости найти ближайшую по L_1, L_{inf}
## Задача про &sum; max (x_i - x^*, y_i - y^*) &rarr; min
## Fractional cascading для параллельных бинпоисков
## Дерево Ли-Чао (dynamic convex hull)

<br> 
# Ещё несколько структур данных
## RMQ-Offline
## Disjoint Sparse Table (аналог на массиве)
## Centroid Decomposition: RMQ за O(1) на дереве
## HLD: считать и от пути, и от отрезка

<br>
# Доказательство  Splay-Tree (и версии с Link-Cut)