pranet's blog

Are range updates possible on 2-D segment trees?
By pranet, history, 8 years ago, In English

I was trying to implement the following functions on a N * N grid in O(log^2(N)) time:

  1. Update: Add v to all grid points in specified rectangle. (v, rectangle are specified in this update)

  2. 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).

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

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

YES

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

P.S. lazy propagation does not work in 2D as far as I know

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

Old thread about this problem. It seems to be really hard (or impossible?) to do this in time per query.

→ Reply