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-Direction (like OX axis).

Whether we can Index Tree in 2-Direction (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-direction. 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 ? :)