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

silloJanuary 25, 2010 at 8:35 PM

Yes, you are correct. Thanks for pointing out the bug.

fR0DDYJanuary 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. SailerFebruary 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?

silloFebruary 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

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

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

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

fR0DDYMay 4, 2011 at 8:59 AM

Thanks for your clarification. I’m loving your works posted here :)

LBMay 13, 2011 at 11:28 PM

Hello, is there possibility to sum all numbers in some interval? If yes, how ?

Great article btw :)

ChrisJune 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))

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

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

asdOctober 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 ?

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

amanMarch 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?

amanMarch 30, 2012 at 9:52 AM

what is the point of thinking behind line 47: cur = ((cur * mul + add) % MAX);

would you kindly explain it?

Thanks in advance

moremathDecember 25, 2012 at 9:05 PM

That is just generating random index values.

fR0DDYDecember 25, 2012 at 9:56 PM

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)]

vermashubhangDecember 10, 2013 at 9:13 PM