Обновление диапазона и запрос к массиву

Question

У меня есть обновления и запросы к массиву A с n элементами.
У меня есть два типа запросов:
тип 1 (обновление): задано x, декрементзначение всех элементов в массиве A, значение которых больше или равно x.
type 2 (Query): Учитывая (l, r, x), найдите x-й наименьший элемент в массиве A, значение которого находится между l иr (оба включительно).

Я не мог придумать лучшего решения, кроме грубой силы, которое могло бы быть таким же дорогим, как O (q * n).Есть ли оптимальное решение?Элементы массива A могут достигать 10 ^ 18.

Answer 1

Структура данных, о которой я думаю, представляет собой расширенный вариант самобалансирующегося двоичного дерева, такого как AA-дерево.В дополнение к обычным элементам каждый узел также хранит количество декрементов, которые неявно применяются к его потомкам.Вместо того, чтобы когда-либо изменять сами числа, чтобы увидеть конечное значение узла, вычтите число декрементов из каждого из его узлов-предков.Каждый узел также ведет подсчет своих потомков.

Обновление состоит из поиска с привязкой по дереву (сложность O(log n)) и увеличения счетчика декрементов O(log n) узлов.В некоторых случаях вам также придется перемещать элементы чуть ниже границы в это дерево (потому что они не меньше, чем все элементы, благодаря уменьшению), что также составляет O(log n).(Обратите внимание, что для этого последнего бита необходимо немного сложное обновление потомков, но я не думаю, что оно нарушает общую границу.)

Операция «запрос» проста;двоичный поиск, чтобы найти l (r не имеет значения для операции, AFAICT), а затем использовать счетчик потомков, чтобы ускорить поиск k-го наименьшего в этом диапазоне до O(log k).

обе операции имеют время O(log n), а общее время - O(q*log n), при условии, что вы не учитываете время O(n*log n) для построения исходного дерева.

Answer 2

Нет лучшего решения, чем выполнение каждого из описанных запросов быстрее, чем O(n), где n - это число элементов вашего массива последовательно в несортированном массиве, когда вы описываете свою проблему.Это потому, что вы должны учитывать каждый элемент в массиве для ваших запросов.Проблема в том, что у вас нет информации о ваших данных, поэтому вы никогда не будете знать, где проверить, чтобы сделать вещи быстрее.

Если вы сделаете много запросов, вы можете провести некоторую оптимизацию, отсортировав свой массив и сохранив его отсортированным.Хотя сортировка сначала займет O(n log(n)) (Quicksort, Mergesort), она позволит вам выполнить запрос в O(log(n)) (или в худшем случае O(n)), используя модифицированный бинарный поиск (найдите первый наименьший элемент в вашем диапазоне, а затем возьмитеследующие х элементов).(Если вы используете библиотечную сортировку, такую ​​как qsort, вы будете сортировать что-то вроде 1.3 nlog (n), что действительно хорошо)

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

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

Если вы не должны сортировать свои данные (для целей построения графиков или около того), то линейное время - лучшее, на что вы можете надеяться.Кроме того, сортировка не нужна, если ваш массив небольшой, он будет излишним и не принесет заметных улучшений.И, честно говоря, линейное время действительно хорошо на современных компьютерах.