Деревья отрезков (7 мая 2018)

  1. C операциями снизу
    1. Общая идея для "суммы на отрезке".
    2. Хранение: индексация, как в куче; листья, начиная с n.
    3. Код функций get, change.
    4. Рисунок, показывающий, что мы работаем не с деревом, а с лесом
    5. Памяти 2n, время ответа на запрос O(log(r-l)), малая константа.
  2. C операциями сверху
    1. Обычный запрос (по аналогии с BST)
    2. Операции += и min. Операции = и +.
    3. Памяти 2n ≤ x ≤ 4n → 2n ≤ x ≤ 3n
  3. Динамическое (для массивов длины ∼109)
    1. Сверху
    2. Снизу
    3. Offline и сжатие координат.
  4. Персистентное: операции сверху. Можно сразу динамическое.

  5. 2D дерево
    1. Дерево отрезков сортированных массивов: сколько чисел на отрезке [L..R] имеют значение от x до y?
    2. Дерево отрезков сортированных массивов: k-я статистика на отрезке за O(log3n).
    3. Равносильность 2D-запроса на массиве и 2D-запроса на плоскости
    4. Дерево отрезков декартовых деревьев: тоже самое, но можно менять y-ки
    5. Дерево отрезков деревьев отрезков.
    6. Многомерный случай: k-мерное дерево отрезков
− Перерыв −
  1. Ортогональные запросы и сканирующая прямая
    1. Для каждой точки посчитать, сколько прямоугольников её покрывают. Offline за O(nlogn) и сжатие координат.
    2. Для каждого прямоугольника посчитать число точек в нём. Offline за O(nlogn) и сжатие координат.
    3. Online версии предыдущих двух задач = persistent scanline + бинпоиск во время запроса
    4. [skipped] [В практику] Задача "даны отрезки на прямой, запрос: сколько пересекаются с отрезком-запросом"
    5. [skipped] [В практику] Количество пар вложенных отрезков на прямой

  2. k-я порядковая статистика за O(log2n) и O(logn).
    1. Вспомогательная задача для понимания спуска по дереву: k-я единица в массиве − решение бинпоиском по ответу за O(log2n), решение спуском по дереву
    2. O(log2n): персистентное дерево отрезков ⇒ ∀ l, r ∃ t[l], t[r+1] ⇒ бинпоиск по ответу
    3. O(logn): параллельный спуск по двум деревьям

  3. [skipped] [В практику] Какая операция подходит для дерева отрезков: ассоциативная, аддитивная (min, max, sum, product матрица, gcd, композиция перестановок, количество отрезков белого цвета)
  4. [skipped] [В практику] Задача "числа добавляются, удаляются, говорить количество чисел со значением от L до R".
− Перерыв −
  1. Fractional cascading
  2. КД-дерево
  3. КД-дерево для получения всех точек в прямоугольнике за O(k + logn)
  4. Количество точек в полуплоскости (persistent + sqrt decomposition + 4-tree)