Как получить максимальное количество пересечений в дереве интервалов после обновления и получить интервал, где это происходит?

Question

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

Вы можете заметить, что эти вопросы очень похожи на эти два вопроса https://cs.stackexchange.com/questions/18611/efficient-algorithm-for-finding-maximum-subset-of-intersecting-rectangles и Максимальное количество перекрывающихся прямоугольников .

Я придерживаюсь аналогичного подхода к основным ответам на эти два вопроса.Сначала я разделяю прямоугольники на два сегмента: нижнюю часть, где он начинается (открытый интервал), и верхнюю часть, где он заканчивается (конечный интервал).И затем сортируйте эти новые сегменты на основе их значения х.Сделав это, я бы создал дерево интервалов и начал бы проходить через сегменты, если я столкнулся с открытым интервалом, я бы добавил его в дерево интервалов, а если я столкнулся с конечным интервалом, я удалил бы его из дерева интервалов.И, наконец, в ответах на эти два вопроса говорится: Мне нужно будет отслеживать максимальное количество пересечений после каждого обновления (это часть, с которой у меня возникают проблемы)

В этих ответах они говорят, что отслеживание максимального числа пересечений после каждого обновления займет O (1) время .

Единственный способ, которым я могу найти решение, - это иметьмассив Интервалы и массив A, где каждый Интервал [i] является либо началом, либо концом интервала, а A [i] будет иметь счетчик количества прямоугольников, пересекающихся в Интервалах [i].Чтобы при добавлении или удалении интервала я мог обновлять А и Интервалы с помощью бинарного поиска, а затем обновлять значения в А от начала нового интервала до конца.Но это дало бы мне O (2 * log (n) + (interval_end - interval_beginning)) линейное решение (в худшем случае, когда добавляемый или удаляемый интервал окружает все остальные интервалы).

Формально формулируя проблему: Как я могу получить максимальное количество интервалов, пересекающихся после обновления в O (1) или O (log (n)) времени?

Воткод для моего решения в Python.Функция, которая берет в открытый и конечный сегменты и выводит максимальное количество пересекающихся интервалов:

import bisect

def max_intersections(segments):
    # Segments have format ((a, b), (c, d), 'b') for open segments
    # And ((a, b), (c, d), 'e') for ending segments
    max_count = 0
    intervals = []
    A = []
    segments = sorted(segments, key=lambda x: (x[0][0], x[2])) # Process open segments first

    for segment in segments:
        if segments[2] == 'b':
            # Open segment, insert interval

            index_beginning = bisect.bisect_left(intervals, segment[0][1])
            intervals.insert(index_beginning, segment[0][1])

            index_end = bisect.bisect_right(intervals, segment[1][1])
            intervals.insert(index_end, segment[1][1])

            # Add one to all elements in A[index_beginning:index_end + 1]
            for i in range(index_beginning, index_end + 1):
                A[i] += 1
                max_count = max(A[i], max_count) # Keep track of the maximum

        else:
            # End segment, remove interval

            index_beginning = bisect.bisect_left(intervals, segment[0][1])
            index_end = bisect.bisect_right(intervals, segment[1][1])

            # Subtract one to all elements in A[index_beginning:index_end + 1]
            # Before removing the elements

            for i in range(index_beginning, index_end + 1):
                A[i] -= 1
            intervals.pop(index_end)
            intervals.pop(index_beginning)

    return max_count

В коде могут быть небольшие ошибки, но общая логика алгоритма есть (Пожалуйста, перейдителегко для меня).

Как вы можете видеть на каждом шаге, я выполняю два двоичных поиска и перебираю все индексы между interval_beginning - interval_end.В худшем случае интервал будет охватывать все другие интервалы, проходя через все позиции в A, давая время O (N ^ 2). Что можно сделать, чтобы функция max_intersections занимала O (N * log (N)) время?