Задачи на тему дерево отрезков (23 марта 2016)

1. get(i, x) = min j ≥ i : a[j] ≥ x за O(logn)
2. Даны N точек на плоскости, get(y1, y2, x1) = есть ли точка (x,y) : y1 ≤ y ≤ y2; x ≤ x2; add(x,y), del(x,y) за O(logn).
3. Дерево отрезков сортированных массивов: get(i, j, x, y) : i ≤ k ≤ j, x ≤ a[i] ≤ y.
1. Количество: длина отрезка за O(1)
2. Сумма: частичные суммы за O(1)
3. Минимум: дерево отрезков за O(logn)
4. Количество различных чисел на отрезке за O(logn)
5. Динамическое (разреженное) дерево отрезков. Как альтернатива сжатию координат.
6. Персистентное дерево отрезков.
7. Решение задачи (3) scanline-ом
1. Offline = дерево отрезков
2. Online = персистентное дерево отрезков
8. k-я порядковая статистика на отрезке за O(logn)