UCI-Night's blog

Help with a problem
By UCI-Night, 11 years ago, In English

Someone can help me to solve this problem, I try Quad-tree but i got TLE. Update Sub-Matrix & Query Sub-Matrix

  • Vote: I like it
  • -4
  • Vote: I do not like it

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

Two dimensional lazy-loading tree (segment tree with lazy propagation) can be used.

Firstly you should try to solve simpler task, with two-dimensional segment tree: - Update one element of matrix - Query sum of sub-matrix

Then you can change segment tree to lazy-loading tree.

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

    how to make lazy tags when dealing with two dimensional seg-tree,I used to think that it is impossible....

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

      Yeah, you' re right — it won't work.

      → Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

It's a straightforward Fenwick-tree problem in two dimensions. If you don't have any idea on how to solve this, it would be better to begin with a one-dimensional version like PYRSUM

Sketch of the idea behind both questions: Topcoder thread, Petr's blog

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

    You are wrong. Both queries asks about sub-matrix.

    Using quad tree you can reach O(N * K) ~ 10^8 with a big constant factor, i think it is not very easy to pass 1 sec TL using quad-tree.

    → Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

This is a new technique for me, i think is really interesting and useful. I used it in Pyramid Sum 2(SPOJ), yesterday.

hex539 wrote a very good article in topcoder. Range BIT updates

→ Reply