Дополнительные главы алгоритмов. Лекция 9

Запросы в многомерных прямоугольниках

• Одномерный случай. Решение двоичным поиском.
• Дерево отрезков.
• Двумерное дерево отрезков. Сжатое двумерное дерево отрезков.
• Многомерное дерево отрезков.
• Решение двумерной задачи с помощью персистентного дерево отрезков.
• Запрос в сжатом двумерном дереве отрезков за O(log n) с помощью дополнительных ссылок вниз.
• Fractional Cascading. Двоичный поиск одновременно в k списках.
• Динамическая задача. Использование BB-alpha деревьев.
• Поиск списка точек в параллелепипеде в 3D.

Рекомендованный материал: лекции MIT, лекции 3 и 4.

Страница лекции на сайте Computer Science Center