UCI-Night's blog

Help with a problem
By UCI-Night, 13 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

»
13 years ago, hide # |
 
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
»
13 years ago, hide # |
← 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
»
13 years ago, hide # |
← 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