Introduction to competitive programming

Binary Index Tree

While learning Some advanced data structures I found Binary Index tree,One of the most intresting data Structure and easy to learn if we are familiar with some bit manipulation Techniques.

I found some tutorials on Internet with great Explanation.

Tutorial 1
Tutorial 2

Also Topcoder had excellent explanation about BIT

Here is the C++ implementation of above Algorithm

//C++ implementation of Binary Index Tree
//Array with N elements
//Construction of BIT
//Initialisation
//Updation
//Query Sum of elments in rangle l...r
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int a[100+1],BIT[100+1],n;
void init()//Initialisation of BIT
{
	for(int i=1;i<=n;i++)
	{
		int val=a[i];
		int idx=i;
		while(idx<=n)
		{
			BIT[idx]+=val;
			idx+=(idx & -idx);
		}
	}
	cout<<"After Initialisation \n";
	for(int i=1;i<=n;i++)
		cout<<BIT[i]<<" ";
	cout<<endl;
}
void update(int pos,int val)//Update the from that Position
{
	int idx=pos;
	while(idx<=n)
	{
		BIT[idx]+=val;
		idx+=(idx & -idx);
	}
	cout<<"After Updation \n";
	for(int i=1;i<=n;i++)
		cout<<BIT[i]<<" ";
	cout<<endl;
}
int query(int idx)
{
	int sum=0;
	while(idx>0)
	{
		sum+=BIT[idx];
		idx-=(idx & -idx);
	}
	return sum;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	memset(BIT,0,sizeof BIT);
	init();
	int q;
	cin>>q;	
	while(q--)
	{
		int t;
		cin>>t;
		if(t==1)
		{
			int x,val;
			cin>>x>>val;
			update(x,val);
		}
		else
		{
			int x,y;
			cin>>x>>y;
 
			cout<<query(y)-query(x-1)<<endl;
		}
 
	}
}