I was trying to implement the following functions on a N * N grid in O(log^2(N)) time:
Update: Add v to all grid points in specified rectangle. (v, rectangle are specified in this update)
Query: Print maximum value in specified rectangle. (rectangle is specified in this query)
I tried implementing a 2-D segment tree, but got stuck with the range updates part (lazy propagation in 2-D dimensions is not pretty)
Is it even possible to do so? (anything below O(N) per operation is fine).
