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

1. Add marble to box i
2. 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 a position in idx of the last digit 1 (from left to right) in binary notation, 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 
using namespace std;  
template class BIT 
{       
	T *tree;       
	int maxVal;       
public:  BIT(int N)       
	{ 
               tree = new T[N+1];
               memset(tree,0,sizeof(tree)*(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 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;
     }
  }