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