Деревья отрезков - бонусная часть (30 апреля 2021)

1. КД-дерево
   1. Общая идея. Что умеет?
   2. Доказательство времени n^1/2 на запрос
   3. Получения всех точек в прямоугольнике за O(k + logn)
   
   
2. Fractional Cascading
   1. Запрос за O(logn) для дерева отрезков сортированных массивов
   2. Найти в каждом из k массивов lowerbound не за O(klogn), а за O(k + logn).
   
   
3. Количество точек в полуплоскости
   1. Решение для малого n: есть всего n² разных поворотов
   2. Решение для большого n (nlogn и 3 из 4 веток рекурсии)
   3. Объединяем