2D Segment Tree with range multiplication, is it possible?

Revision en1, by bochet, 2015-07-01 17:49:51

Hi all,

This is my first blog in Codeforces. I met an optimisation problem in my work. The problem can be simplified as this:

we need to perform two operations on a matrix A:

  1. multiply a sub matrix (given xmin, xmax, ymin, ymax) of A by a constant c_i
  2. query the sum of a sub matrix of A

My first idea is to use 2D segment tree with range update because I have seen and solved problems like (1) 2D segment tree for rmq, (2) 1d segment tree with range multiplication. But after spending one day trying to combine 2d segment tree with range multiplication, I found it very difficult (or maybe impossible ?) to do that because the two nodes may intersect, for example:

..x. .... ..x. xxxx ..x. .... ..x. ....

will intersect at point (2, 3), and that makes everything so hard!

I can switch to quadtree to avoid such a problem, but then it means the single operation complexity would go from O(log(W)*log(H)) to O(W+H).

So can you help me with this problem?

Tags segment tree, range update, 2d trees

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English bochet 2015-07-01 17:55:50 6
en2 English bochet 2015-07-01 17:53:35 150
en1 English bochet 2015-07-01 17:49:51 1053 Initial revision (published)