As you know Binary Index Tree, include two method Sum_tree, Insert_tree. To indexing and get total prefix of tree with complexity O(log(n)) (n is max size of tree) In detail
void insert_tree(int idx)
{
while(idx<=n)
{
tree[idx]++;
idx+=(idx&(-idx));;
}
}
int sum_tree(int idx)
{
int tg=0;
while(idx>0)
{
tg+=tree[idx];
idx-=(idx&-idx);
}
return tg;
}
Right. It is Binary Index Tree in 1-Dimension (like OX axis).
Whether we can Index Tree in 2-Dimension (Oxy axis). The answer is Yes. We can do it.
For example I have problem below: You have Oxy Axis. Have N query with 3 parameter (t x y), t is 0, it mean we mark point(x,y).Otherwise, it mean we unmark point(x,y). Now have M query with 2 parameter (x,y). With every query output. how many point in rectangle with coordinates [(0,0);(0,x);(0,y);(x,y)].
X ,Y, N<=10^3, M<=10^5. I solved with
void insert_tree(int x,int y,int val)
{
int y1;
while(x<=max_x)
{
y1 = y;
while(y1<=max_y)
{
tree[x][y1]+=val;
y1 += (y1&-y1);
}
x+=(x&-x);
}
}
With function mark point (x,y), you can call insert_tree(x,y,1) and unmark insert_tree(x,y,-1). It's BIT 2-Dimension. You can do same with Sum_tree function, with complexity N*log(N)*log(N) (input) + M*log(N)*log(N) (output). So great. right ? :)
