Binary Indexed (Fenwick) Tree
Fenwick Tree is also known as Binary Indexed Tree (BIT).
The Fenwick Tree is a useful data structure for implementing dynamic cumulative frequency tables.
For example:
Suppose we have test scores of m=11 students $f = {2,4,5,5,6,6,6,7,7,8,9}$. The test scores are integer values ranging from [1..10].
We define the term frequency and cumulative frequency as follows.
The frequency of a test score is the number of times it is appearing in the table. The cumulative frequency of a test score is the sum of frequencies of all the test scores up to that test score.
We can draw the table indicating these as follows:
Index/Score Frequency Cumulative Frequency cf
0 | - | -
1 | 0 | 0
2 | 1 | 1
3 | 0 | 1
4 | 1 | 2
5 | 2 | 4
6 | 3 | 7
7 | 2 | 9
8 | 1 | 10
9 | 1 | 11
10 | 0 | 11
The cumulative frequency table can also be used as a solution to the Range Sum Query (RSQ) as discussed at the end of this post: https://rishabhjainiitbhu.blogspot.com/2019/09/segment-trees.html
When the frequencies are static, then the cumulative frequency table can be computed with a simple O(n) loop.
However, when the frequencies are frequently updated (increased or decreased) we use a dynamic data structure.
Instead of using Segment trees we use far simpler Fenwick Tree. Fenwick Tree operations are extremely efficient as they use fast bit manipulation techniques.
We will use the function LSOne(i) (which is: i & (-i) ). LSOne(i) returns the Least Significant One-bit in i. That is it will return the number where the first one bit is in i.
If i is 101100101000 than LSOne will give 1000.
We use vector for implementing Fenwick Tree.
The Fenwick Tree is a tree that is indexed by the bits of its integer keys. These integer keys fall within the range [1 .. n] skipping index 0. In the above table [1 .. 10] are the integer keys in the corresponding array with size n=10 and m=11 data points.
Let the Fenwick Tree be named as ft. ft[i] stores the cumulative frequency of elements.
The element at index i is responsible for elements in the range [i-LSOne(i)+1 .. i]. Thus, ft[i] stores the cumulative frequency of elements {i-LSOne(i)+1, i-LSOne(i)+2 .. i}. For above array ft[4]=2 is responsible for the range [4-4+1 .. 4] = [1 .. 4], ft[6]=5 is responsible for range [6-2+1 .. 6] = [5 .. 6], so on and so forth.
{---------------------------------------------------------}10
{--------------------}2 |
{------}1 | {---------}5 | {------}1
0 | 0 | 2 | 2 | 1 |
| | | | | | | | | |
Index/Key: 0 1 2 3 4 5 6 7 8 9 10
In Binary 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010
Freq(cum) 0(0) 0(0) 1(1) 0(1) 1(2) 2(4) 3(7) 2(9) 1(10) 1(11) 0(11)
{---} denotes the ranges
With such an arrangement, if we want to obtain the cumulative frequency between [1 .. b], i.e. rsq(b), we simply add ft[b], ft[b'], ft[b''] .. until $b^i$ is zero.
Here b' = b - LSOne(b). This strips off the least significant one-bit of b at each step. An integer has only O(log b) bits, rsq(b) runs O(log n) times, when b=n.
Try drawing diagram for the above tree. rsq(6) = ft[6] + ft[4], this because the indices 4 and 6 are responsible for range [1 .. 4] and [5 .. 6] respectively. By combining them, we account for the entire range of [1 .. 6].
With rsq(b) available, obtaining the cumulative frequency between two indices [a..b] where a!=1 is simple, rsq(a,b) = rsq(b)-rsq(a-1). This is also an O(logn) time task when b=n.
Updating
Updating the value of the element at index k by adjusting its value by v, i.e. calling adjust(k,v) we have to update ft[k], ft[k'], ft[k''].... until $k^i$ exceeds n. But this time k' = k + LSOne(k). If you adjust(k,v) it will add 1 to ft[k] at indices k=5=101, k'=(101)+(001)=110 and k''=(110)
+(010)=1000=8 via the expression given above.
Notice that if you project a line upwards from index 5 in the figure, the line intersects that ranges under the responsibility of index 5, index 6, and index 8.
Fenwick tree thus supports both RSQ and update operations in just O(n) space complexity and O(logn) time complexity, given a set of m integer keys that ranges from [1 .. n]. This makes Fenwick Tree an ideal DS for solving dynamic RSQ problems.
Here is the code for Fenwick Tree
| #include <bits/stdc++.h> | |
| using namespace std; | |
| typedef vector<int> vi; | |
| class FenWickTree{ | |
| private: vi ft; | |
| public: FenWickTree(int n){ | |
| ft.assign(n+1, 0); | |
| } | |
| int LSOne(int b){ | |
| return b&-b; | |
| } | |
| int rsq(int b){ | |
| int sum=0; | |
| for (; b; b-=LSOne(b)) { | |
| sum += ft[b]; | |
| } | |
| return sum; | |
| } | |
| int rsq(int a, int b){ | |
| return rsq(b)-(a==1?0:rsq(a-1)); | |
| } | |
| void adjust(int k, int v){ | |
| for(;k<(int)ft.size();k+=LSOne(k)){ | |
| ft[k] += v; | |
| } | |
| } | |
| }; | |
| int main(int argc, char const *argv[]) { | |
| int f[] = { 2,4,5,5,6,6,6,7,7,8,9 }; // m = 11 scores | |
| FenWickTree ft(10); | |
| for (int i = 0; i < 11; i++) ft.adjust(f[i], 1); // this is O(k log n) | |
| printf("%d\n", ft.rsq(1, 1)); // 0 => ft[1] = 0 | |
| printf("%d\n", ft.rsq(1, 2)); // 1 => ft[2] = 1 | |
| printf("%d\n", ft.rsq(1, 6)); // 7 => ft[6] + ft[4] = 5 + 2 = 7 | |
| printf("%d\n", ft.rsq(1, 10)); // 11 => ft[10] + ft[8] = 1 + 10 = 11 | |
| printf("%d\n", ft.rsq(3, 6)); // 6 => rsq(1, 6) - rsq(1, 2) = 7 - 1 | |
| ft.adjust(5, 2); // update demo | |
| printf("%d\n", ft.rsq(1, 10)); // now 13`` | |
| return 0; | |
| } |
Grab a pencil and draw the things out.
No comments:
Post a Comment