Monday, October 10, 2016

Fenwick Tree

I will start with a quote that I think is really appropriate with this post. The quote is from Brian Cantwell Smith, he said

Just because you've implemented something doesn't mean you understand it.

The same applies to the tree I am describing below. I implemented the tree a while ago and think I understand it, but I didn't. Now I finally understand it.

The code is really simple. The problem this tree is trying to solve is to have a $ O(\log n) $ time update and $ O(\log n) $ time query for running sum. We can achieve that with a segment tree, but that will take $ O(n \log n) $ space, this one take only $ O(n) $ space.

Despite the deceptive simplicity in the code is the theory behind it. To start with, we look at a decomposition of a range into power of 2 ranges. To make thing interesting, let's consider the range [1..13]

The range can be decomposed into

[1..8] [9..12] [13]

How about [1..6], that would be decomposed into

[1..4] [5..6]

So here is the set of all the interesting ranges (if the maximum range we are interested is [1..13])

[1] [1..2] [1..4] [1..8]
[3]
[5] [5..6]
[7]
[9] [9..10] [9..12]
[11]
[13]

And interesting way to visualize these ranges is as follow

         13
   12
   11    11
   10 10
   9  9  9
8
7        7
6     6
5     5  5
4  4
3  3     3
2  2  2
1  1  1  1

One interesting observation is that if we hit the scan line from the right to the left, we can always find a range, for example, shooting a ray from the 6, we get the range [5, 6]. We said 6 is responsible for [5, 6]

So suppose we have computed the sum for all of these ranges, then we can easy compute any running sum easy by walking the 'stairs'.

For example, if we want to compute the sum [1..7], we can go like this.

         13
   12
   11    11
   10 10
   9  9  9
8
7        7
6     6
5     5  5
4  4
3  3     3
2  2  2
1  1  1  1

This is exactly what the running sum operation in the tree trying to do. Note that every time we walk down the stair, the responsible indices are eliminating the least significant bit that is a 1. The bit operation index = index - (index & -index) do exactly that.

Update is more interesting. This time around whenever a value change in the array, we need to update all ranges that contains the value. That is simply walking towards the right hand side. For example, we wanted to update the value for index 5, that gives the following walk.

         13
   12
   11    11
   10 10
   9  9  9
8
7        7
6     6
5     5  5
4  4
3  3     3
2  2  2
1  1  1  1

Geometrically, this is easy enough. But how do we actually walk the responsible indices? By reading the code, that is index = index + (index & -index). What exactly does that mean in terms of the bits? That means eliminating the least significant bit that is 1 by adding 1 to it and carry upwards, you can see that it does work for this case.

5 -> 0101
6 -> 0110
8 -> 1000 

In general it does work for all case, and that's how a fenwick tree works.

Finally, I grok the concept!

No comments :

Post a Comment