Как выполнить обновление диапазона в sqrt{n} времени?

Question

У меня есть массив, и я должен выполнить запрос и обновления на нем. Для запросов мне нужно найти частоту определенного числа в диапазоне от l до r, а для обновления мне нужно добавить x из некоторого диапазона от l до r.

Как это сделать?

Я думал об оптимизации sqrt {n}, но я не знаю, как выполнить обновление диапазона с такой временной сложностью.

Редактировать - так как некоторые люди просят пример, вот один

Предположим, что массив имеет размер n = 8

и это

1 3 3 4 5 1 2 3

И есть 3 вопроса, чтобы помочь всем объяснить, что я пытаюсь сказать

Вот они

q 1 5 3 - Это означает, что вы должны найти частоту 3 в диапазоне от 1 до 5, которая равна 2, так как 3 появляется на 2-й и 3-й позиции.

во-вторых, запрос на обновление, и он выглядит так - u 2 4 6 -> Это означает, что вы должны добавить 6 в массиве в диапазоне от 2 до 4. Таким образом, новый массив станет

1 9 9 10 5 1 2 3

И последний запрос снова такой же, как и первый, который теперь будет возвращать 0, поскольку в массиве с позиции 1 до 5 теперь нет 3.

Я верю, что сейчас все должно быть яснее.:)

Answer 1

Я разработал этот алгоритм давно (20+ лет назад) для арифметического кодера. Обновление и извлечение выполняются в O(log(N)).

Я назвал этот алгоритм "Метод интервалов". Позвольте мне показать вам пример.

Представьте себе, у нас 8 интервалов с номерами 0-7:

+--0--+--1--+--2-+--3--+--4--+--5--+--6--+--7--+

Давайте создадим дополнительный набор интервалов, каждый из которых порождает пару оригинальных:

+----01-----+----23----+----45-----+----67-----+

После этого мы создадим дополнительный слой с интервалами, порождаем пары второго:

+---------0123---------+---------4567----------+

И наконец, мы создаем один интервал, охватывающий все 8:

+------------------01234567--------------------+

Как вы видите, в этой структуре, чтобы извлечь правую границу интервала [5], вам просто нужно сложить длину интервалов [0123] + [45]. чтобы получить левую границу интервала [5], вам нужна сумма длин интервалов [0123] + [4] (левая граница для 5 - это правая граница для 4). Конечно, левая граница интервала [0] всегда = 0.

Когда вы внимательно посмотрите на эту предложенную структуру, вы увидите, что лишние элементы в каждом слое не нужны. Я говорю, вам не нужны элементы 1, 3, 5, 7, 23, 67, 4567, так как эти элементы не используются, во время поиска или обновления.

Позволяет нам удалить нечетные элементы и сделать следующее вознаграждение:

+--1--+--x--+--3-+--x--+--5--+--x--+--7--+--x--+
+-----2-----+-----x----+-----6-----+-----x-----+
+-----------4----------+-----------x-----------+
+----------------------8-----------------------+

Как видите, с этим вознаграждением используются цифры [1-8]. Позвольте им быть индексами массива. Итак, вы видите, что используется память O(N).

Чтобы получить правую границу интервала [7], вам нужно было добавить длину значений с индексами 4,6,7. Чтобы обновить длину интервала [7], вам нужно было добавить разницу ко всем 3 из этих значений. В результате оба поиска и обновления выполняются за время журнала (N).

Теперь необходим алгоритм, как по исходному интервальному числу вычислить множество индексов в этой структуре данных. Например - как конвертировать:

1 -> 1
2 -> 2
3 -> 3,2
... 
7 -> 7,6,4

Это легко, если мы увидим двоичное представление для этих чисел:

1   -> 1
10  -> 10
11  -> 11,10
111 -> 111,110,100

Как видите, в каждой цепочке следующее значение - это предыдущее значение, где крайнее правое "1" изменено на "0". Используя простую битовую операцию "x & (x - 1)", мы можем создать простой цикл для итерации индексов массива, связанных с номером интервала:

int interval = 7;
do {
  int index = interval;
  do_something(index);
} while(interval &= interval - 1);