COME ON CODE ON

A blog about programming and more programming.

Binary Indexed Tree (BIT)

with 19 comments

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

  1. Topcoder Tutorial

NJOY!
-fR0D

About these ads

Written by fR0DDY

September 17, 2009 at 11:40 PM

19 Responses

Subscribe to comments with RSS.

  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?
    Thanks in advance

    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


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 227 other followers

%d bloggers like this: