Use case
Using a Fenwick tree it requires only O(log n) operations to compute any desired cumulative sum, or more generally the sum of any range of values (not necessarily starting at zero).
Implementation
Fenwick trees are implemented as an implicit data structure using a flat array analogous to implementations of a binary heap. Given an index in the array representing a vertex, the index of a vertex's parent or child is calculated through bitwise operations on the binary representation of its index.
Pre - Isolating the last set bit
Given the number x =1110 in binary, how to extract its last bit that is not 0?
x&(-1) will give us this last bit of number x.
Why?
Say x = a1b, where a is some binary sequence of any length of 1’s and 0’s and b is a sequence of any length of 0’s only.
-x = 2's complement of x = (a1b)' + 1 = a'0b' +1 = a'0(1....1)+1 = a'1(0...0) = a'1b
(a1b) &(a'1b) = (0...0)1(0...0)
This is used to subtract the last bit of index from itself (i.e., set the least significant non-zero bit of index to zero)
Relationship between BIT and input array
Suppose that we want to find the cumulative frequency at index 13(1101 in binary).
cum[1101] = BIT[1101] + BIT[1100] + BIT[1000]
BIT[i] stores the cumulative sum from the index
i to I-r+1 (both inclusive), where r represents the last set bit in the index i.
if a is the input array, let's take a look at how the BIT[6] is calculated.
BIT[6] = a[6]+a[5]
6 -- 0110
4 -- 0100
BIT[0110] only sum numbers from 0110 to 0100+1
We strip the last 1 by 6-2+1 = 5
2 -- 0010
Sum of first 8 elements = BIT[8]
Sum of first 6 elements = BIT[6] + BIT[4]
Sum of first 12 elements = BIT[12] + BIT[8]
Sum of first 14 elements = BIT[14] + BIT[12] +BIT[8]
Note: a[6] is 6th element in the given array -- index starting at 1
You can see that only index that is exactly equal to power of 2 contains elements all the way down to a[1], others need to start stripping down the last bit. Input array a is indexed starting at 1.
How to Construct BIT
We call update() operation for each element of given array to construct the Binary Indexed Tree.
You can use "diff" as value when some entry in array has changed.
//add "val" at index "x"
void update(int x, int val) {
for(; x <= n; x += x&-x)
BIT[x] += val;
}
For example, a[4] should not only in BIT4 but also in BIT[8] (BIT[1000])
a[1] is added to:
BIT[1] -- 0001
BIT[2] -- 0010
BIT[4] -- 0100
BIT[8] -- 1000
a[3] is added to:
BIT[3] -- 0011
BIT[4] -- 0100
BIT[8] -- 1000
a[6] is added to:
BIT[6] -- 0110
BIT[8] --1000
a[7] is added to:
BIT[7] -- 0111
BIT[8] --1000
Work Flow
When a table value is modified, all range sums which contain the modified value are in turn modified during a similar traversal of the tree.
How to get cumulative sum
int cumu(int x)
{
int sum = 0;
for(; x > 0; x -= x&-x)
sum += BIT[x];
return sum;
}
def cumsum(x):
sum = 0
while x>0:
sum += BIT[x]
x -= x&(-x)
return sum
#if array index starting at 0, index 5--7
sum_from_6th_to_8th_inclusive = cumsum(8) - cumsum(5)
