Дерево отрезков со сканирующей прямой, 2D-деревья (24 февраля)

  1. Дерево Merge Sort-а: 2D-orthogonal-query в online за O(log2n)
  2. Биекция N точек и массива (2D запрос на точках и 2D запрос на массиве − одно и то же)
  3. Многомерные запрос [Lx ≤ x ≤ Rx, Ly ≤ y ≤ Ry, Lz ≤ z ≤ Rz, ... ] (дерево отрезков деревьев отрезков деревьев отрезков). Ответ на запрос за время O(logdn), за время O(logd-1n).
  4. Дерево отрезков с запросами снизу
  5. Дерево Фенвика
  6. Многомерное дерево Фенвика (версия для двухмерного массива)
  7. Сканирующая прямая: 2D-orthogonal-query в offline за O(logn)
  8. Cканирующая прямая: максимальная возрастающая подпоследовательность точек (а заодно вспоминаем решение бинарным поиском)