Вторая лекция

1. LZSS
1. Алгоритм сжатия текста, простейшая реализация
2. Динамика для подсчета LCP, реализация за O(N²), O(N²) памяти
3. Подсчет LCP за O(N²) с использованием Z-функции и O(N) памяти
4. С точки зрения суф.дерева LCP = LCA
5. Решение cуф.массивом: построили, нашли ближайший слева-справа за O(1) с предподсчетом O(N)
6. LCP(любой пары суффиксов) считается бинпоиском с хешами за O(logN)
7. А еще бинпоиском с хешами за O(Nlog²N) строится суф.массив.
2. Простейшее 2D-дерево для N точек
1. Сортим точки по X
2. На массиве строим дерево отрезков сортированных массивов
3. Build: for merge
4. Get: поднимаемся снизу, бинпоиск
5. Преимущества Get снизу перед Get сверху
3. Структуры данных − корневая эвристика
1. Разбиение исходного множества на куски по √ N 
1. Пример1: ближайший справа ноль и a[i]=1
2. Пример2: orders --- maximize(l, r, up to x), getSum(l, r)
2. Отолженные операции (разбиение множества запросов на куски по √ N )
1. Пример: 2D-Count, Add point, Del point
3. Идея про строки: max длина не более √ SumLen 
4. Идея про Split: можно делать reverse, код становится короче