Обновление диапазона + запрос диапазона с двоичными индексированными деревьями

10

Я пытаюсь понять, как двоичные индексированные деревья (деревья Фенвика) могут быть изменены для обработки как запросов диапазона, так и обновлений диапазона.

Я нашел следующие источники:

http://kartikkukreja.wordpress.com/2013/12/02/range-updates-with-bit-fenwick-tree/ http://programmingcontests.quora.com/Tutorial-Range-Updates-in-Fenwick-Tree http : //apps.topcoder.com/forums/ модуль = Thread & ThreadId = 756271 & Start = 0 & Мс = 4 # 1579597

Но даже после прочтения всех их я не мог понять, какова цель второго двоичного индексированного дерева или что оно делает.

Может кто-нибудь объяснить мне, как двоичное индексированное дерево модифицируется, чтобы справиться с этим?

data-structures binary-trees search-trees 1110101001
источник

Ответы:

9

Предположим, у вас был пустой массив:

0  0  0  0  0  0  0  0  0  0  (array)
0  0  0  0  0  0  0  0  0  0  (cumulative sums)

И вы хотели обновить диапазон от +5 до [3..7]:

0  0  0  5  5  5  5  5  0  0  (array)
0  0  0  5 10 15 20 25 25 25  (desired cumulative sums)

Как вы можете хранить желаемые совокупные суммы, используя 2 дерева с двоичными индексами?

Хитрость заключается в том, чтобы использовать два дерева с двоичными индексами, BIT1 и BIT2, где совокупная сумма рассчитывается по их содержанию. В этом примере вот что мы будем хранить в двух деревьях:

0   0   0   5   5   5   5   5   0   0  (BIT1)
0   0   0  10  10  10  10  10 -25 -25  (BIT2)

Чтобы найти sum[i], вы рассчитываете это:

sum[i] = BIT1[i] * i - BIT2[i]

Например:

sum[2] = 0*2 - 0 = 0
sum[3] = 5*3 - 10 = 5
sum[4] = 5*4 - 10 = 10
...
sum[7] = 5*7 - 10 = 25
sum[8] = 0*8 - (-25) = 25
sum[9] = 0*9 - (-25) = 25

Чтобы достичь желаемых значений BIT1 и BIT2 для предыдущего обновления диапазона, мы делаем 3 обновления диапазона:

  • Нам нужно обновить диапазон +5 до индексов 3..7 для BIT1.

  • Нам нужно обновить диапазон +10 до индексов 3..7 для BIT2.

  • Нам нужно обновить диапазон от -25 до индексов 8..9 для BIT2.

Теперь давайте сделаем еще одно преобразование. Вместо того, чтобы хранить значения, показанные выше для BIT1 и BIT2, мы фактически сохраняем их кумулятивные суммы. Это позволяет нам выполнить 3 обновления диапазона выше, выполнив 4 обновления кумулятивных сумм:

BIT1sum[3] += 5
BIT1sum[8] -= 5
BIT2sum[3] += 10
BIT2sum[8] -= 35

В общем случае алгоритм добавления значения v в диапазон [i..j] будет выглядеть так:

BIT1sum[i]   += v
BIT1sum[j+1] -= v
BIT2sum[i]   += v * (i-1)
BIT2sum[j+1] -= v * j

где синтаксис + = и - = просто означает обновление структуры данных накопленной суммы BIT с положительным или отрицательным значением в этом индексе. Обратите внимание, что когда вы обновляете совокупную сумму BIT по индексу, она неявно влияет на все индексы справа от этого индекса. Например:

0 0 0 0 0 0 0 0 0 0 (original)

BITsum[3] += 5

0 0 0 5 5 5 5 5 5 5 (after updating [3])

BITsum[8] -= 5

0 0 0 5 5 5 5 5 0 0 (after updating [8])

О(журнал⁡N)

СП1
источник
Какова была ваша первоначальная мотивация в создании BIT2, а затем в получении sum[i] = BIT1[i] * i - BIT2[i]? Кажется, что это работает, но это кажется настолько произвольным ... какое понимание позволяет вам прийти к этому?
1110101001
3
Ну, я не изобрел этот алгоритм. Я читаю это так же, как ты. Но следует заметить, что когда вы добавляете обновление диапазона, ваши кумулятивные суммы становятся возрастающей последовательностью (5, 10, 15, 20, ...). БИТЫ не хранят увеличивающиеся последовательности как это. Но если вы сохраните константу (5) в BIT и умножите значение BIT на индекс, вы получите увеличивающуюся последовательность, такую ​​же, как вы хотите. Тем не менее, вам нужно исправить начало и конец последовательности. Вот для чего второе дерево.
JS1
В целом хорошо, но меня смутило то, что вы написали «Вместо того, чтобы хранить значения, показанные выше для BIT1 и BIT2, мы на самом деле храним их кумулятивные суммы» - я бы сказал, что вы на самом деле делаете обратное, то есть сохраняете дельты ,
j_random_hacker