_spartan's blog

Range Updates in 2-D Binary Indexed Tree
By _spartan, 10 years ago, In English

I have been learning 2-D BIT lately.

But I am having difficulty implementing range updates in it.

Eg. Suppose we have a matrix M[][].There are 2 types of queries:

1.ADD x1 y1 x2 y2 val

This adds val to all matrix elements which have their x-coordinate between x1 and x2 and y-coordinate between y1 and y2.

2.SUM x1 y1 x2 y2

This query returns the sum of all matrix elements which have their x-coordinate between x1 and x2 and y-coordinate between y1 and y2.

I am having trouble implementing the first query using 2-D BIT.

Had point(x1, y1) and point(x2, y2) been same, following code would work :

void update(int x1, int y1, ll val)

{

int x, y;

x=x1;

while(x<=n){

    y=y1;

    while(y<=m){                  //Update y coordinate

       ft[x][y]+=val;        //ft stores BIT

       y+=(y&-y);

    }

    x+=(x&-x);

}

return;

}

How to go about it if I have to update the whole range?

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

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm not sure you can do this in a simple way using BIT

You need to use 2D segment Trees

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    2-D segment tree times out.

    This can be solved using 4 2-D BITs.I found this paper mentioned by CtrlAlt helpful.

    → Reply
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

This kind of problems cannot be solve using regular BIT (using only one BIT) since regular BIT doesn't support range update.

This problem is similar with USUBQSUB on SPOJ, solution using Range Update BIT explained here http://mirror.codeforces.com/blog/entry/8874#comment-146017

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    is not really true, BIT does not support range update and range sum at the same time, but we can simply implement range update and single element query

    → Reply
»
10 years ago, # |
  Vote: I like it +6 Vote: I do not like it

I suppose this paper would be useful for you.

→ Reply