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 in:↵
↵
..x. ....↵
..x. xxxx↵
..x. ....↵
..x. ....http://mirror.codeforces.com/predownloaded/72/63/7263f47bb299330d4dc4a4c3d2e81b848bd87920.png↵
↵
will intersect at point (2, 3) and other points, 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?↵
↵
↵
↵
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 in:↵
↵
..x. xxxx↵
..x. ....↵
..x. ....
↵
will intersect at point (2, 3) and other points, 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?↵
↵
