The Fenwick tree is more popularly known as the Binary Indexed Tree which works solves the Range Sum Queries problems. The same can be achieved by a Segment Tree or a RMQ but the BIT wins big time in terms of simplicity.
It server two primary queries:
- Update index I by value V
- Get sum of all elements from index 0..I
- Runtime O(logN)
It stores the sum of elements in nearest powers of two and is implemented in a simple array. The main idea being to update the nearest powers of two everytime we have an update on the array and fetch the sum of all elements from 0..i by looking at these nearest powers of two.
For updates at index- We add the element to the present value of the element and propagate the value all the way till the top of the array on the closest powers of two.
For obtaining the sum we start at the given end index and keep adding the numbers by the reverse technique all the way till the end.
private int getNext(int index){
return index + (index & -index);
}
private int getPrev(int index){
return index - (index & -index);
}
22 = 16 + 4 + 2
SUM(1,22) = SUM(1,16) + SUM(17,20) + SUM(21,22)
To understand how the next and previous values are derived here are the values all the way from 1 to 16. Note for (i – (i& -1)) the values of 11 which points to 10, and 10 points to 8 (nearest power of 2)
i i - (i & -i) i + (i & -i) 1 0 2 2 0 4 3 2 4 4 0 8 5 4 6 6 4 8 7 6 8 8 0 16 9 8 10 10 8 12 11 10 12 12 8 16 13 12 14 14 12 16 15 14 16 16 0 32
Read :