Ортогональные запросы

• 1D статическая задача. Массив + бинпоиск.
• 1D динамическая задача. BST.
• 2D статическая задача за \(\log^2 n\). 2D дерево.
• 2D статическая задача за \(\log n\). Бинпоиск + переход по ссылкам.
• 2D динамическая задача за \(\log^2 n\). Балансировка по весу.
• Обобщение для больших размерностей. Просто добавь деревьев.
• 3D статическая задача за \(\log n\). Fractional cascading.

Нахождение многоугольника по точке

• Offline задача. Сканирующая прямая.
• Online задача. Персистентное дерево.
• Сложность по времени и памяти.