Fancy Coder

share my projects and discoveries

Binary Indexed Tree

Binary Indexed Tree (also called Fenwick tree), a good tutorial is available here

Binary indexed tree’s logical structure is an integer array. Initially array is filled with 0. Binary Indexed Tree allows you to update value of element in array, and compute sum of elements in any index interval. All operations are O(log n).

The implementation is simple and efficient, although quite tricky, and it is very popular in programming contests. Source code follows.

//index from 1 to N
template<size_t N>
class BinaryIndexedTree{
	int *a;
	int low_bit(int x){return x & -x;}
public:
	// i \in [1,N]
	void add(int i,int k=1){
		while(i<=N){
			a[i]+=k;
			i+=low_bit(i);
		}
	}
	// i \in [0,N]
	int sum(int i){
		int res=0;
		while(i){
			res+=a[i];
			i-=low_bit(i);
		}
		return res;
	}
	// i \in [0,N], j \in [i,N]
	int rangeSum(int i,int j){
		return sum(j)-sum(i-1);
	}
	BinaryIndexedTree(){
		a=new int[N+1];
		fill(a,a+N,0);
	}
	~BinaryIndexedTree(){
		delete[] a;
	}
};
Advertisements

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 )

Google+ photo

You are commenting using your Google+ 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 )

w

Connecting to %s

%d bloggers like this: