Binary Indexed Tree (BIT)
In this post we will discuss the Binary Indexed Trees structure. According to Peter M. Fenwick, this structure was first used for data compression. Let’s define the following problem: We have n boxes. Possible queries are
- Add marble to box i
- Return sum of marbles from box k to box l
The naive solution has time complexity of O(1) for query 1 and O(n) for query 2. Suppose we make m queries. The worst case (when all queries are 2) has time complexity O(n * m). Binary Indexed Trees are easy to code and have worst time complexity O(m log n).
The two major functions are
- update (idx,val) : increases the frequency of index idx with the value val
- read (idx) : reads the cumulative frequency of index idx
Note : tree[idx] is sum of frequencies from index (idx – 2^r + 1) to index idx where r is rightmost position of 1 in the binary notation of idx, f is frequency of index, c is cumulative frequency of index, tree is value stored in tree data structure.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| f | 1 | 0 | 2 | 1 | 1 | 3 | 0 | 4 | 2 | 5 | 2 | 2 | 3 | 1 | 0 | 2 |
| c | 1 | 1 | 3 | 4 | 5 | 8 | 8 | 12 | 14 | 19 | 21 | 23 | 26 | 27 | 27 | 29 |
| tree | 1 | 1 | 2 | 4 | 1 | 4 | 0 | 12 | 2 | 7 | 2 | 11 | 3 | 4 | 0 | 29 |
Table 1.1
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| tree | 1 | 1..2 | 3 | 1..4 | 5 | 5..6 | 7 | 1..8 | 9 | 9..10 | 11 | 9..12 | 13 | 13..14 | 15 | 1..16 |
Table 1.2 – table of responsibility
Here’s a C++ template code :
#include<iostream>
using namespace std;
template<class T>
class BIT
{
T *tree;
int maxVal;
public:
BIT(int N)
{
tree = new T[N+1];
memset(tree,0,sizeof(T)*(N+1));
maxVal = N;
}
void update(int idx, T val)
{
while (idx <= maxVal)
{
tree[idx] += val;
idx += (idx & -idx);
}
}
//Returns the cumulative frequency of index idx
T read(int idx)
{
T sum=0;
while (idx>0)
{
sum += tree[idx];
idx -= (idx & -idx);
}
return sum;
}
};
int main()
{
int a[100],cur=1,mul=2,add=19,MAX=65536,x,i;
//Initialize the size by the
//maximum value the tree can have
BIT<int> B(MAX);
for (i=0;i<50;i++)
{
a[i] = cur;
B.update(a[i],1);
cur = ((cur * mul + add) % MAX);
}
while (cin>>x)
{
cout<<B.read(x)<<endl;
}
}Resources:
NJOY!
-fR0D
Hi,
pretty nice class, but shouldn’t you use this instead on line 13?
memset(tree,0,sizeof(tree)*(n+1));
sillo
January 25, 2010 at 8:35 PM
Yes, you are correct. Thanks for pointing out the bug.
fR0DDY
January 25, 2010 at 9:17 PM
Hello. Very nice Post. Not really what i have searched over Google, but thanks for the information.
Andrew A. Sailer
February 1, 2010 at 4:51 AM
Sorry, I have to correct myself. Recently I was told that you should use
memset(tree,0,sizeof(int)*(N+1));
because sizeof(tree) should equal sizeof(int*) and that does not have to be the same size as sizeof(int).
However I had no problems with sizeof(tree). Maybe coincidence?
sillo
February 2, 2010 at 2:44 PM
The above example of course if T is int. (I implemented this without template, that’s why I made the example with integer. You might just replace int with T)
Cheers
sillo
February 2, 2010 at 2:50 PM
tree is a pointer. So, sizeof(tree)*(N+1) = 4*(N+1). It should be sizeof(T)*(N+1).
Rohil
November 1, 2010 at 10:25 PM
Hi, Thanks for ur post. Would u mind to explain why tree[15] stores frequency of c[15] only. Here idx = 15 (in binary, 1111). So, r = 3, Hence tree[15] is supposed to store c[] values from idx – 2^r + 1 = 15 – 2^3 + 1 = 8 to to c[idx]. I can’t get it at all. Pls help.
Thanks.
LB
May 4, 2011 at 3:09 AM
Hi,
The rightmost position of 1 in idx is 0 and not 3. “r is a position in idx of the last digit 1 (from left to right) in binary notation”. So r=0 and hence 15-2^0+1=15. It is a little confusing, I will change it to rightmost position of 1 in binary notation.
fR0DDY
May 4, 2011 at 8:59 AM
Thanks for your clarification. I’m loving your works posted here
LB
May 13, 2011 at 11:28 PM
Hello, is there possibility to sum all numbers in some interval? If yes, how ?
Great article btw
Chris
June 18, 2011 at 1:06 AM
yes.. possible.. if we want to sum all numbers b/w x and y… just call the binary indexed tree with
sum=func(y)-func(x-1);
this will giv u the answer
time complexity ( 2*log(n))
vishnuvarthan
July 18, 2011 at 7:18 PM
Dang it, i wrote incorrectly, i meant update all numbers in some interval for value X.
And i don’t want to update each number in single update. Thanks for any tips.
Chris
July 26, 2011 at 4:12 PM
Hey does ur code give the sum of all the elements from index i to index j . I suppose it can only give sum of all elements from value X to value Y.
asd
October 5, 2011 at 3:58 PM
Suppose we have n boxes numbered from 0 to N-1. For this if we update frequency for idx = 0 , infinite loop runs in while loop.Does this mean , for this solution idx >= 1 always ?
vagrawal13
December 31, 2011 at 10:09 AM
Hey very nice post on BIT, may i ask you to add little about segment and interval trees. I am not clear about segment/interval trees and their similarity with BIT.
aman
March 29, 2012 at 9:41 AM
hey you wrote a problem at the beginning of this post which is not discussed above. Can you please explain how BIT solves that problem in specified time?
aman
March 30, 2012 at 9:52 AM