Renamed's blog

By Renamed, history, 9 years ago, In English

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

  • Vote: I like it
  • +3
  • Vote: I do not like it

| Write comment?
»
9 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Anyone know. how to solve this problem with other way ? :)

»
9 years ago, # |
  Vote: I like it +7 Vote: I do not like it

it's dimension not direction

»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

"Fenwick tree" is more popular than "BIT". But thank for your contribute.