# COME ON CODE ON

A blog about programming and more programming.

## 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

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 sum=0;
while (idx>0)
{
sum += tree[idx];
idx -= (idx & -idx);
}
return sum;
}
};

int main()
{
//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)
{
}

}```

Resources:

NJOY!
-fR0D

Written by fR0DDY

September 17, 2009 at 11:40 PM

### 20 Responses

1. 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

2. 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

3. 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

4. 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

5. 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

6. 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

7. 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

8. 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

9. 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

10. 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

11. what is the point of thinking behind line 47: cur = ((cur * mul + add) % MAX);
would you kindly explain it?

moremath

December 25, 2012 at 9:05 PM

• That is just generating random index values.

fR0DDY

December 25, 2012 at 9:56 PM

12. The code in case of 2D Binary Indexed Trees for update and query is simple but I didn’t get how to initialize the value of the Tree array in 2D. As in case of 1D array the value is
Tree[i] = cummulative[i] – cummulative[ i – (i&-i)]

vermashubhang

December 10, 2013 at 9:13 PM

13. […] comeoncodeon.wordpress.com/2009/09/17/binary-indexed-tree-bit/ […]