Вот два подхода к решению этой проблемы с деревьями сегментов:
Подход 1
Вы можете использовать дерево сегментов отсортированных массивов.
Как обычно, дерево сегментов делит ваш массив на ряд поддиапазонов разного размера. Для каждого поддиапазона вы сохраняете отсортированный список записей плюс кумулятивную сумму отсортированного списка. Затем вы можете использовать бинарный поиск, чтобы найти сумму записей ниже вашего порогового значения в любом поддиапазоне.
Получив запрос, вы сначала обрабатываете поддиапазон O(log(n)), который охватывает ваш диапазон [a,b]. Для каждого из них вы используете двоичный поиск O (log (n)). В целом это сложность O(qlog^2n) для ответа на q запросов (плюс время предварительной обработки).
Подход 2
Вы можете использовать динамическое дерево сегментов.
Дерево сегментов позволяет отвечать на запросы вида «Вычислить сумму элементов от a до b» за время O(logn), а также изменять одну запись за время O(logn).
Поэтому, если вы начинаете с пустого дерева сегментов, вы можете повторно вставить записи в порядке возрастания. Предположим, мы добавили все записи от 1 до 5, поэтому наш массив может выглядеть так:
[0,0,0,3,0,0,0,2,0,0,0,0,0,0,1,0,0,0,4,4,0,0,5,1]
(Нули представляют записи, которые больше 5, поэтому они еще не были добавлены.) На этом этапе вы можете отвечать на любые запросы, порог которых равен 5.
В целом это будет стоить O(nlog(n)) для добавления всех записей в дерево сегментов, O(qlog(q)) для сортировки запросов и O(qlog(n)) для использования дерева сегментов для ответов на запросы. .
person
Peter de Rivaz
schedule
14.07.2017
