kllp's blog

A question about 2d data structure
By kllp, 12 years ago, In English

M is an n*n matrix. Is it possible to code a data structure that supports these operations:

  • addValue(x1, x2, y1, y2, a): Adds a to every element M[y1...y2][x1...x2]. Should work in O(log^2 n).
  • getMin(x1, x2, y1, y2): Returns minimum from elements M[y1...y2][x1...x2]. Should work in O(log^2 n).

I tried to solve this with 2d segment tree but nothing works because of the min QAQ

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

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

Treap of Segment trees :)

→ Reply
»
12 years ago, hide # |
 
Vote: I like it +12 Vote: I do not like it

What does QAQ mean?

→ Reply