запросить количество пересеченных сегментов в ярости

Question

У меня есть большой набор данных сегментов (ai, bi), где ai < bi, и много запросов. Каждый запрос запрашивает количество пересекаемых сегментов с заданным диапазоном (b, e). Количество запросов может быть очень большим. Наивный алгоритм состоит в том, чтобы искать все пересекающиеся сегменты на запрос, что, по-видимому, занимает O (N) времени. Есть ли более быстрый способ сделать это? Я могу представить, что сортировка набора данных сегментов в порядке возрастания ai может помочь, но я не знаю, что делать в другом направлении.

segments: [1, 3], [2, 6], [4, 7], [7, 8] 
query 1: [2, 5] => output [1, 3] [2, 6], [4, 7]
...

Answer 1

Составьте список B отсортированных начальных точек, как вы написали.

Составьте список P структур, содержащих все точки - как начальные, так и конечные точки вместе с полем SE = +1/-1 для начала и конца соответственно . Сортировать по координате точки.

Сделать Active = 0. Пройдите через P, добавив SE к Counter и создав новый список A, содержащий позицию точки и Active счетчик.

Для каждого запроса запускайте поиск (с двоичным поиском) нижней позиции в A, получить Active - количество открытых сегментов в данный момент.

Затем поиск по индексам в B, соответствующих началу и концу запроса, получить разность индексов - количество сегментов, начинающихся внутри интервала запроса.

Требуется сумма этих значений number of intersected segments (сами сегменты согласно постановке задачи не нужны)

Время на запрос O(log(N))

[1, 3], [2, 6], [4, 7], [7, 8]                       initial list
[1, 2, 4, 7]                                         list B
(1,1),(2,1),(3,-1),(4,1),(6,-1),(7,-1),(7,1),(8,-1)  list P
(1,1),(2,2),(3,1), (4,2),(6,1), (7,0), (7,1),(8,0)   list A 
        ^
q start 2 gives active = 2 (two active intervals)

searching 2 in B gives index 1, searching 5 gives index 2, 
difference is 1  
result = 2 + 1 = 3