Начал смотреть лекцию ШАД "Задачи геометрического поиска". Там обсуждается следующая задача:
есть 3 типа запросов на прямой:
1. Добавить интервал (l..r)
2. Удалить интервал (l..r)
3. Вывести все интервалы, содержащие точку x
В лекции не стали рассказывать полное решение. Было лишь сказано, что задача решается путем построения сбалансированного дерева, ключами которого являются левые границы интервалов.
В лекции сказано, что эту задачу можно решать за асимптотику O(k + logn) на запрос 3 (и видимо за O(logn) на остальные запросы), насколько я понял.
Можете объяснить решение, которое подразумевалось в лекции, либо посоветовать литературу по этому вопросу?
Также, если предложенное в лекции решение не оптимально, то интересна оценка и доказательство асимптотики такого алгоритма.
Я не слушал лекцию, но мне на ум с ходу приходит тупое решение за O(n * log n * [асимптотика set-а]) с помощью дерева отрезков (в вершинах дерева отрезков храним set-ы, выполняем добавление отрезка как прибавление на отрезке без проталкивания вниз).
Не совсем понял какое дерево отрезков. Я вроде бы знаю решение с ДО, где в каждой вершине v(которой соответствует отрезок [l..r]) храним сет правых концов отрезков, левые концы которых принадлежат [l..r]. Тогда добавляя/удаляя отрезок нам нужно изменить log set-ов. А при ответе на 3 запрос, нам нужно для каждой вершины v(ей соответствует [l..r] и [l..r] полностью содержится в [1..x]) вывести некоторое количество самых максимальных элементов из set-a.
P.S. Данное решение, как выяснилось, нормально работает только в случае, если каждая координата является началом не более 1 отрезка. В противном случае, предложенный мной алгоритм может требовать O(n^2) памяти
Я понял так: в каждой вершине ДО храним множество индексов отрезков, полностью покрывающих отрезок [l;r], причем если индекс лежит в множестве вершины, то он не лежит в множествах её детей, т.е. когда мы добавляем новый элемент на отрезок, не нужно пропихивать его вниз. Теперь на запрос третьего типа нужно пройти log вершин и выписать все индексы в множествах. Это будет O(log^2 n * ans), потому что каждый индекс не более раза выпишем.
Да, моя идея именно такая.
Приходит на ум следующее: будем хранить сбалансированное дерево (к примеру, декартово), которое хранит отрезки, упорядоченные по левому концу. При запросе 3его типа:
1).Рассплитим дерево, отделим только те отрезки, чьи левые концы находятся не правее нашей точки.
2). Будем дополнительно хранить в вершине дерева координату максимального правого конца среди всех интервалов в поддереве данной вершины.
3). Запустим дфс, который заходит только в вершины, где максимальный правый конец не левее нашей точки.
4). Утверждается, что это будет работать за O(K + log N), потому что в сбалансированном дереве наддерево наших К выделенных вершин содержит порядка 2K вершин, ну и в дфсе мы не опустимся глубже чем на O(logN) вершин.
Для этого есть стандартная для вычислительной геометрии структура данных, которая называется Interval tree (русское название: дерево интервалов, name clash с деревом отрезков). Статья на википедии: Interval tree
Как решать, когда запрос 3 — вывести интервалы, содержащие заданный интервал?
Аналогично описанному мною выше. В п.2 заменить "нашей точки" на "левого конца нашего интервала", в п.4 заменить "нашей точки" на "правого конца нашего интервала".
Спасибо! Интересно, а можно решить деревом отрезков с set-ами как описано выше?