Задачи на массивах

1. Если массив не меняется (длина N)
1. Сумма на префиксе за O(1)
2. Сумма на отрезке за O(1)
3. Минимум на префиксе за O(1)
4. Минимум на отрезке фиксированной длины за O(1)
5. Минимум на произвольном отрезке за O(1) с предподсчетом O(NlogN)
2. Если массив меняется
1. Одномерное дерево отрезков.
2. Дерево Фенвика (для суммы)

Задачи на матрицах

1. Если матрица не меняется (ширина W, высота H)
1. Сумма в углу за O(1)
2. Сумма в прямоугольнике за O(1)
3. Минимум в углу за O(1)
4. Минимум в прямоугольнике фиксированного размера за O(1)
5. Минимум на произвольном прямоугольнике за O(1) с предподсчетом O(WHlogWlogH)
2. Если массив меняется
1. Двумерное дерево отрезков на матрице
2. Двумерное дерево Фенвика на матрице (для суммы)

Двумерные деревья

1. КД-дерево за [O(NlogN), O(N), O(sqrtN)]
1. Сортировка точек, храним 2 перестановки.
2. Делим или на четном уровене по X, на нечетном по Y. У каждой вершины 2 сына.
3. Время работы O(sqrtN).
4. КД-дерево эквивалентно одномерному дереву отрезков.
2. Not read Квадро-дерево
1. Not read Решеаем задачу о площади пересечения/объединения кругов приближенно.
2. Not read Еще одна задача: найти не покрытую точку.
3. 2D дерево отрзков за [O(NlogN), O(NlogN), O(log²N)] (жесть)
1. Набор точек фиксирован. Координаты фиксированы. Значения в точках можно менять.
2. Запрос за O(log²N). Минус по сравнению с КД-деревом.

Функции на путях дерева в online

1. Путь = сумма двух вертикальных путей (через LCA)
2. Дерево не меняется.
1. Длина пути за O(1) + LCA.
2. Сумма на пути за O(1) + LCA.
3. Минимум на пути за O(logN) (двоичные подъемы)
3. Дерево меняется
1. Эйлеров обход и одномерное дерево отрезков для суммы.
2. Not read Покрытие дерева массивами (деревьями отрезков)
3. Сведение задачи к прямоугольному запросу на плоскости и 2-мерным деревьям.

Функции на путях дерева в offline

1. Дерево не меняется.
1. LCA в offline за O(1*);
2. dfs по дереву рулит
3. Решение RMQ на дереве одномерным деревом отрезков.