Деревья отрезков (10 мая 2017)

  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 + бинпоиск во время запроса
  2. k-я порядковая статистика за O(log2n) и O(logn).
    1. O(log2n): персистентное дерево отрезков ⇒ ∀ l, r ∃ t[l], t[r+1]
    2. O(logn): параллельный спуск по двум деревьям
    3. Вспомогательная задача для понимания спуска по дереву: k-я единица в массиве − решение бинпоиском по ответу, решение спуском
− Перерыв −
  1. Fractional cascading
  2. КД-дерево
  3. КД-дерево для получения всех точек в прямоугольнике за O(k + logn)
  4. Количество точек в полуплоскости (persistent + sqrt decomposition + 4-tree)