Binary Index Tree 2-Dimension

Revision en3, by Renamed, 2015-09-14 17:47:29

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 ? :)

Tags bit, bitmask, 2-dimension

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English Renamed 2015-09-14 17:47:29 26
en2 English Renamed 2015-09-14 13:22:27 58
en1 English Renamed 2015-09-14 13:20:08 1436 Anyone know solve this problem with another way ? (published)