Деревья отрезков (13 мая 2025)

1. Мотивация
   1. Сама структура данных новые операции делать не умеет, но имеет меньше константу
   2. Это не только структура данных, но и идея, как можно представлять массив
   
   
2. Простейшее дерево отрезков
   1. Идея для n=2^k
   2. Хранение на массиве (индексация, как в куче)
   3. Основная теорема: любой отрезок разбивается на ≤ 2logn вершин дерева отрезков (2 на каждом уровне)
   4. Запрос сумма: снизу
   5. Запрос сумма: сверху
   6. Запрос изменить 1 элемент: снизу
   7. Запрос изменить 1 элемент: сверху
   
   
3. Полностью снизу
   1. Хранение: индексация, как в куче; листья, начиная с n.
   2. Код функций get, change.
   3. Рисунок, показывающий, что мы работаем не с деревом, а с лесом
   4. Памяти 2n, время ответа на запрос O(log(r-l)), малая константа.
   
   
4. Полностью сверху
   1. Обычный запрос (по аналогии с BST)
   2. Операции += и min. Операции = и +.
   3. Памяти 2n ≤ x ≤ 4n → x=2n-1 (Эйлеров обход)
   
   
5. Динамическое (для массивов длины ∼10⁹)
   1. Сверху (ссылки)
   2. Снизу (hashmap)
   3. Offline и сжатие координат.
   4. Персистентное: операции сверху. Можно сразу динамическое.
   
   
6. Чем 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. Для каждого префикса храним множество ⇒ умеем считать 2D.
   2. НВП за O(nlogn)
   
   
3. Ортогональные запросы и сканирующая прямая
   1. Для каждой точки посчитать, сколько прямоугольников её покрывают. Offline за O(nlogn) и сжатие координат.
   2. Для каждого прямоугольника посчитать число точек в нём. Offline за O(nlogn) и сжатие координат.
   3. Online версии предыдущих двух задач = persistent scanline + бинпоиск во время запроса
   4. [skipped] [В практику] Задача "даны отрезки на прямой, запрос: сколько пересекаются с отрезком-запросом"
   5. [skipped] [В практику] Количество пар вложенных отрезков на прямой
   
   
4. 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): параллельный спуск по двум деревьям
   
   
5. [skipped] Фенвик (не успеем?)
   
6. [skipped] Задачи
   1. [skipped] [В практику] Какая операция подходит для дерева отрезков: ассоциативная, аддитивная (min, max, sum, product матрица, gcd, композиция перестановок, количество отрезков белого цвета)
   2. [skipped] [В практику] Задача "числа добавляются, удаляются, говорить количество чисел со значением от L до R".