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.