Saturday, 3 May 2014

binary indexed tree code

Here I am writing  c/c++ code for implementing simple binary index tree (BIT). I will upload the explanation after some time.
A request from all the blog reader please suggest me the topics on which i can upload the tutorials.
mail me @ :- raj.nishant360@gmail.com
// © NISHANT RAJ
// source :-> http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees
// created :-> 23 / 03 / 2014 ; 04 : 36
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <map>
#include <string>
#include <cstring>
#include <sstream>
#include <fstream>
#include <climits>
#include <ctime>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
int a[100000],cum[100000],res[100000],maxval;
int get_value(int idx) // reading cumulative frequency of index idx O(log(maxval 
{
   int sum=0;
   while(idx>0)
  {
     sum+=res[idx];
     idx-=(idx & -idx);
  }
  return sum;
}
void update(int idx,int val)// updating frequency range 
{
   while(idx<=maxval)
  {
     res[idx]+=val;
     idx+=(idx & -idx);
  }
}
int main()
{
   int t;
   cin>>t;
   while(t--)
  {
    int j,idx,val,k;
    cin>>maxval;
    cum[0]=0;
    for(int i=1;i<=maxval;i++)
   {
     cin>>a[i];   //actual frequency given by user.
   cum[i]+=a[i]+cum[i-1];// cumulative frequency array.
  }
  for(int i=1;i<=maxval;i++)
  {
   j= i + 1 - (1<<(__lg(i & -i)));// __lg(num) ->calculates                                                        //the position of MSB
   res[i]=cum[i] - cum[j-1];// calcualting frequency of particular range
 }
  int qury;
  cin>>qury;
  string in,upd="U",find="S";
  while(qury--)
  {
   cin>>in;
   if(in==upd)
   {
    cin>>idx>>val;
    update(idx,val); // takes O(log(maxval)) time.
   }
   if(in==find)
   {
    cin>>j>>k;   // takes 2*O(log(maxval)) time.
    cout<<(get_value(k) - get_value(j-1))<<endl;
   }
  }
 }
 return 0;
}

No comments:

Post a Comment

Thank you for reading and commenting my blog.