Hello everyone!

My friend and I were discussing range update and range query of maximum in two dimensions and I am not sure how to implement such a data structure. It appears to be much more difficult than range query/update in one dimensions as it is hard to propagate a tree.

Can anyone provide any insight on this?

Thanks in advance

It's impossible to achieve log^2 worst case time complexity. But you can use quad tree instead, which gives O(N) per update/query.

?? But there is 2D segment tree for queries with such complexity... += and sum on range are possible with log^2 complexity.

Can you handle other types of queries apart from submatrix-sum queries (with range updates) using 2D Segment Trees in ? Something like max or min?

Personally I can't even handle += and sums :)

I just know that it's possible

That's a much too strong statement to be left with positive number of votes and without evidence at the same time.

Comment ratings on Codeforces rarely make any sense

Sum queries can surely be handled with updates in .

Max/Min seems hard.

I was talking about max/min, though what you are talking about is not what is usually called 2d-queries.

What you have done allows to perform rectangle queries and updates on 2d-array of size, like, 1000x1000.

But the more common problem is when you have, like, 10

^{5}points in the plane with arbitrary coordinates, each point is assigned with some weight and you are asked to perform two kinds of queries: getting sum of weights of all points belonging to a rectangular region and increasing weights of all points belonging to a rectangular region by some constant.This also can be done in per query, but I only know an approach that requires memory and that is completely inefficient. The best choice for such a problem would be using an sqrt-decomposition rather than a

log^{2}napproach.But what exactly is wrong with nested BSTs solution? Its space requirement would be .

Yes max and min functions are also possible.

Edit: I haven't seen that it's with updates. No 2d segment trees can't handle 2d rectangle updates. As each row update will have different cols ranges so lazy propagation can't be applied.

Add submatrix and query sum of submatrix can be supported using 2D BIT (thus possible using 2D segment tree). But I believe add submatrix and get max on submatrix cannot be done the same way as the 1D case, and quadtree is the best I know for such cases.

But Quad tree is for square grid

n*nnot for

n*mWell, simply view the matrix as max(m,n) * max(m,n) if you want :)

In fact quadtree is built separately on each dimension, so you don't have to make sure the matrix is square.

http://codeforces.com/blog/entry/45157

Hi !

Problem Tetris 3D require a 2D segment tree with update and query on range (it is what you need).

It is possible !

We need 2 segment tree (one main and other for lazy propagation) that every node of this segment trees has 2 segment trees; one main and other for lazy propagation.

It has a log^2 worst case time complexity.

See my code for better understanding.

I've inspected your code:

Have anyone solved this problem now? Or is there any idea about how to prove the lower bound?