Range update + range query with binary indexed trees

Question

I am trying to understand how binary indexed trees (fenwick trees) can be modified to handle both range queries and range updates.

I found the following sources:

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/?module=Thread&threadID=756271&start=0&mc=4#1579597

But even after reading through all of them I could not understand what the purpose of the second binary indexed tree is or what it does.

Could someone please explain to me how the binary indexed tree is modified to handle these?

Answer 1

Suppose you had an empty array:

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

And you wanted to make a range update of +5 to [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)

How could you store the desired cumulative sums using 2 binary indexed trees?

The trick is to use two binary indexed trees, BIT1 and BIT2, where the cumulative sum is calculated from their contents. In this example, here's what we'd store in the the two trees:

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

To find sum[i], you compute this:

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

For example:

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

To achieve the desired BIT1 and BIT2 values for the previous range update, we do 3 range updates:

• We need to do a range update of +5 to indices 3..7 for BIT1.

• We need to do a range update of +10 to indices 3..7 for BIT2.

• We need to do a range update of -25 to indices 8..9 for BIT2.

Now let's do one more transformation. Instead of storing the values shown above for BIT1 and BIT2, we actually store their cumulative sums. This lets us do the 3 range updates above by making 4 updates to the cumulative sums:

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

In general, the algorithm to add a value v to a range[i..j] would be:

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

where the += and -= syntax simply means to update the BIT cumulative sum data structure with a positive or negative value at that index. Note that when you update the BIT cumulative sum at an index, it implicitly affects all indices to the right of that index. For example:

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])

Fenwick trees store sums in a binary tree. It is easy to do the updates shown above to a Fenwick tree, in $O(\log n)$ time.