Point Updates in Fenwick Tree

Question

I have a hard time understanding how does adding LSB to the current index gives us the next place which contains the given point.

void update(int k, int x) {
    while (k <= n) {
        tree[k] += x;
        k += k&-k; // adding LSB (least significant bit)
    }
}

Can anyone explain to me or refer to some resources? All the resources I've seen just tell you that it works, but does not explain why. I know how the query works though.

Thanks.

P.S I've seen kind of the same questions here, but I don't still get it, since they do not really explain.

Answer 1

Fenwick Tree data structure can be quite tricky to grasp fundamentally, but once you understand the underlying mathematics, you should be good at it. So I will try to explain all the hows and whys about Fenwick Trees.

Fenwick Tree is based on the Binary Representation of the array index

First and foremost, what you should firmly understand is, that:

Idea of the Fenwick Tree is based on a fact, that each integer number can be represented as a Binary Number, i.e. as a sum of different powers of 2, and that representation will be unique; e.g. integer number 14 can be represented as 2³+2²+2¹.

^{Note, that "different", is important keyword in this definition, so you should not represent 14 as 23+21+21+21.}

How Fenwick Tree is populated

I will not implement the Fenwick Tree population algorithm here (you said, you understand how the tree is populated, besides, it is irrelevant to the question); however, I will stress the fact, that Fenwick Tree is [mostly] implemented via array, in a way, that each slot in the fenwick-tree array, holds a value, which is the sum of the range of the original array, where:

1. right index in that range is k itself (this slot is the right bound);
2. number of elements in that range is the smallest addend from the sum-of-the-powers-of-two representation of that index (so, you should count that amount of elements, from right, to the left, in order to get the range in question).

P. S. If the Fenwick Tree stores some n value at index 24, this means, that sum of the interval [17, 24] in the original array, will be n.

Q: Why 17 is the left bound?
A: Because, 24 is 2⁴+2³, and smallest addend from this expression is 2³ = 8. Now, according to the definition given above, the range which sums up to the element at index 24 in the Fenwick Tree array, will be containing 8 elements, and if the right bound happens to be at index 24 itself, 8 consecutive elements from right to the left will get us to the left bound, which is at index 17; therefore, we have 8 elements in the inclusive range [17, 24] and the value at the index 24 will be n, which is sum of the elements in [17, 24] range.

This image will even clearly illustrate what I wrote above:

Important note:

Representing the integer as a sum of different powers of 2, stems from the principles of the Binary Numeral System.

For instance, 1011 can be written as 2³+2¹+2⁰.

leftmost column, in the binary representation, constitutes 2 to the power of 3, and the right most column constitutes 2 to the power of 0. In the binary representation, powers of 2 increase by 1 per each step from rightmost column to the left.

If you understand the Binary Numeral System, you should understand, that when representing some number N as the sum of the different powers of two, the smallest number in that sum, is same, as the part in N's binary representation starting from the Least Significant Bit (LSB) and ending with the rightmost digit of that binary representation, which is also same as 2 to the power of indexOf(LSB)-1 (in case you start indexing your binary number with 1, from the right) or indexOf(LSB) (in case you index your number with 0).

---

What does all this give?

Faster Range Queries

See how does Range Query work in the Fenwick Tree.

I hope you understand that we need prefix sums for the range queries.

In order to calculate the prefix sums for the original[0, index], instead of iterating over entire array, you now just cascade down in the corresponding Fenwick Tree, from that index, and you continuously remove LSB from the values at those indices, while you keep summing up values at all those indices (which are sums of the ranges of the original array).

This looks like:

int prefixSum(int index) {
    int sum = 0;
    while(index!=0) {
        sum+=fenwickTree[index];
        index = index - LSB(index);
    }
    return sum;
}

Q: Why does this work?
A: I think it should be obvious now, but if it is still not - then pay a close attention on why we remove LSB(index). We do so, because after you have added fenwickTree[index] to the current sum while calculating the prefix sum, as we've already explained above, next slot storing another slice of the original arrays interval, will be at the index = index - LSB(index), because in the Fenwick Tree, indix k stores the interval of the length [2^{LSBIndexOf(toBinary(k))-1}, k]

So, according to what we have just shown (cascading, summing, and index-LSB(index)), with the Fenwick Tree, the prefix sum for index 11 (for example), will be calculated as:

prefixSum = fenwickTree[11] + fenwickTree[10] + fenwickTree[8]

because:

1. fenwickTree[11] stores sum of original[11] (odd indices store only values at those indices);
2. fenwickTree[10] stores sum of original[9,10];
3. fenwickTree[8] stores sum of original[1, 8].

You basically have 3 slices to sum up: [1,8], [9,10] and [11].

Faster Point Updates

See how does Point Update work in the Fenwick Tree.

I think, it is now obvious why and how Point Update works - in terms of LSB, it is an opposite operation of the range query - instead of removing LSB(index), you will be adding the LSB(index), cascading now UP to the indices and updating corresponding ones in the Fenwick Tree.

For instance, if we want to add a value at index 9, you have to find out all the slots that are responsible for that index and you have to update them. We have to take number starting at LSB of index 9 element, and we have to add it to value at index 9. We have to keep repeating this until we reach the slot where LSB is the number at that index itself. That's it.

void update(int i, int x) {
    while (i <= n) {
        fenwickTree[i] += x;
        i += LSB(i); //this will give you the next slot which is used as an addend
    }
}

I really hope this helps you and sheds some light on your understanding.