Подсчитайте количество интервалов, попадающих в данный диапазон

Question

Предположим, у вас есть список интервалов, таких как [(0 4), (1 3), (2 5), (2 6)]. Этот список не отсортирован. Затем вам дается диапазон, такой как [1 5]. Вы должны вернуть количество интервалов, которые соответствуют внутри диапазона. В этой задаче он возвращает 2. ((1 3) и (2 5))

Список интервалов остается постоянным, но нам дается не более 100000 запросов, каждый из которых состоит из диапазона. Для каждого запроса диапазона мы должны возвращать количество интервалов, которые вписываются внутрь.

После исследования я прочитал о Деревья интервалов . Однако вы можете запрашивать только интервалы, которые перекрывают с любым заданным диапазоном, в то время как я ищу интервалы, которые попадают в диапазон . Эти запросы занимают логарифмическое время c.

Есть ли способ решить эту проблему с такой же временной сложностью, возможно, с изменением интервальных деревьев? Я не ищу линейного решения (поскольку грубая сила в любом случае будет означать сканирование через все интервалы).

Answer 1

Добавляя предположения, что эти сегменты не такие длинные, если вы добавите интервал, вы можете запомнить идентификатор в узле дерева и вам нужно будет запомнить только точки пересечения сегментов a и b , поэтому вы просто попросите дерево сегментов получить вектор пересечения идентификаторов a и b. А из другого дерева вы спросите о количестве концовок в сегменте ab. После вы просто удалите идентификатор, который произошел один раз. Это должно быть быстрее.