Деревья отрезков (29 мая 2021)

1. Вступление
   1. Время из общаги? Такси из общаги?
   2. Смотрим код 12A
   3. Пишем код аллокатора
   
   
2. Мотивация
   1. Сама структура данных новые операции делать не умеет, но имеет меньше константу
   2. Это не только структура данных, но и идея, как можно представлять массив
   
   
3. Простейшее дерево отрезков
   1. Идея для n=2^k
   2. Хранение на массиве (индексация, как в куче)
   3. Основная теорема: любой отрезок разбивается на ≤ 2logn вершин дерева отрезков (2 на каждом уровне)
   4. Запрос сумма: снизу
   5. Запрос сумма: сверху
   6. Запрос изменить 1 элемент: снизу
   7. Запрос изменить 1 элемент: сверху
   
   
4. Полностью снизу
   1. Хранение: индексация, как в куче; листья, начиная с n.
   2. Код функций get, change.
   3. Рисунок, показывающий, что мы работаем не с деревом, а с лесом
   4. Памяти 2n, время ответа на запрос O(log(r-l)), малая константа.
   
   
5. Полностью сверху
   1. Обычный запрос (по аналогии с BST)
   2. Операции += и min. Операции = и +.
   3. Памяти 2n ≤ x ≤ 4n → 2n ≤ x ≤ 3n
   
   
6. Динамическое (для массивов длины ∼10⁹)
   1. Сверху (ссылки)
   2. Снизу (hashmap)
   3. Offline и сжатие координат.
   4. Персистентное: операции сверху. Можно сразу динамическое.
   
   
7. Чем BST лучше дерева отрезков?
   1. Умеет вставку в i-е место, удаление, умеет reverse, автоматически динамическое
   2. В персистентном случае ровно n вершин (меньше памяти)

1. 2D дерево
   1. Дерево отрезков сортированных массивов: сколько чисел на отрезке [L..R] имеют значение от x до y?
   2. Дерево отрезков сортированных массивов: k-я статистика на отрезке за O(log³n).
   3. Равносильность 2D-запроса на массиве и 2D-запроса на плоскости
   4. Можно в вершине хранить любую стуктуру данных
      1. Дерево отрезков декартовых деревьев: тоже самое, но можно менять элементы массивов
      2. Дерево отрезков деревьев отрезков
      3. Многомерный случай: k-мерное дерево отрезков (k-1-мерное в вершине)
   
   
2. Ортогональные запросы и сканирующая прямая
   1. Для каждой точки посчитать, сколько прямоугольников её покрывают. Offline за O(nlogn) и сжатие координат.
   2. Для каждого прямоугольника посчитать число точек в нём. Offline за O(nlogn) и сжатие координат.
   3. Online версии предыдущих двух задач = persistent scanline + бинпоиск во время запроса
   4. [skipped] [В практику] Задача "даны отрезки на прямой, запрос: сколько пересекаются с отрезком-запросом"
   5. [skipped] [В практику] Количество пар вложенных отрезков на прямой
   
   
3. k-я порядковая статистика за O(log²n) и O(logn).
   1. Вспомогательная задача для понимания спуска по дереву: k-я единица в массиве − решение бинпоиском по ответу за O(log²n), решение спуском по дереву
   2. O(log²n): персистентное дерево отрезков ⇒ ∀ l, r ∃ t[l], t[r+1] ⇒ бинпоиск по ответу
   3. O(logn): параллельный спуск по двум деревьям
   
   
4. [skipped] Задачи
   1. [skipped] [В практику] Какая операция подходит для дерева отрезков: ассоциативная, аддитивная (min, max, sum, product матрица, gcd, композиция перестановок, количество отрезков белого цвета)
   2. [skipped] [В практику] Задача "числа добавляются, удаляются, говорить количество чисел со значением от L до R".
   
   
5. [skipped] Фенвик (не успеем?)

1. КД-дерево
   1. Общая идея. Что умеет?
   2. Доказательство времени n^1/2 на запрос
   3. Получения всех точек в прямоугольнике за O(k + logn)
   
   
2. Fractional Cascading
   1. Запрос за O(logn) для дерева отрезков сортированных массивов
   2. Найти в каждом из k массивов lowerbound не за O(klogn), а за O(k + logn).
   
   
3. Количество точек в полуплоскости
   1. Решение для малого n: есть всего n² разных поворотов
   2. Решение для большого n (nlogn и 3 из 4 веток рекурсии)
   3. Объединяем