kllp's blog

A question about 2d data structure
By kllp, 11 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

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

Treap of Segment trees :)

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    And how exactly will it help you with this problem?

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

What does QAQ mean?

→ Reply