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

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

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

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