Tutorial for Binary indexed tree
Here i am not giving a tutorial of binary indexed tree. We can use the data structure without knowing how it works. All we need to know is what it does.
Binary Indexed Tree (BIT)
Given a large array. BIT helps us to do the following
1. Update any element a[i] in O(log(n))
2. Query the cumulative value in O(log(n)). query(i) = summation a[k] k=1,2,3,....i
It is faster than segment trees.
#define MAX 100007
int T[MAX+1]; //Define a space for BIT
//function to update
void update(int idx, int val)
//function to query
int query(int idx)
Remember you should never query or update on the 0th element.
that gives an error because your elements are a , a , ....a[n]
so be careful with that.
Some problems you can do with it are: