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

YouTube

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

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

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

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