9
$\begingroup$

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?

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What was your initial motivation in creating BIT2 and then having sum[i] = BIT1[i] * i - BIT2[i]? It seems to work but it seems so arbitrary... what insight allows you to come to this? $\endgroup$ – 1110101001 Nov 13 '14 at 6:20
  • 3
    $\begingroup$ Well I didn't invent this algorithm. I read it just like you did. But one thing to notice is that when you add a range update, your cumulative sums become an increasing sequence (5, 10, 15, 20, ...). BITs don't store increasing sequences like that. But if you store a constant (5) in the BIT, and multiply the BIT value by the index, you get an increasing sequence just like what you want. However, you need to fix up the beginning and end of the sequence. That is what the second tree is for. $\endgroup$ – JS1 Nov 13 '14 at 6:27
  • $\begingroup$ Good on the whole, but I found it confusing that you wrote "Instead of storing the values shown above for BIT1 and BIT2, we actually store their cumulative sums" -- I would say you are actually doing the opposite, i.e., storing the deltas. $\endgroup$ – j_random_hacker May 18 '15 at 20:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.