UCI-Night's blog

By UCI-Night, 7 years ago,

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

• -4

 » 7 years ago, # |   0 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-matrixThen you can change segment tree to lazy-loading tree.
•  » » 7 years ago, # ^ |   +10 how to make lazy tags when dealing with two dimensional seg-tree,I used to think that it is impossible....
•  » » » 7 years ago, # ^ |   0 Yeah, you' re right — it won't work.
 » 7 years ago, # | ← Rev. 2 →   +6 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 PYRSUMSketch of the idea behind both questions: Topcoder thread, Petr's blog
•  » » 7 years ago, # ^ |   -8 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.
•  » » » 7 years ago, # ^ |   +5 At least one Fenwick-tree based approach works; as proof you can see that I solved the problem using this sort of technique already: http://www.spoj.com/status/USUBQSUB,hex539/Actually your comment seems a bit out-of-place- was it supposed to be directed at me?
•  » » » » 7 years ago, # ^ |   0 can you please explain me, or give me a code with 2d fenwick-tree, or 2d lazy propagation? I think it should be O(n) for query.
•  » » » » » 7 years ago, # ^ |   +8 Here's one implementation. (It's XOR-sum, but the idea is the same and the implementation of ordinary sum is easier.) http://codeforces.com/contest/341/submission/4391440
•  » » » » » 7 years ago, # ^ |   0 And a simple linear version, without context: http://pastebin.com/CuuRyRZw
 » 7 years ago, # | ← Rev. 2 →   0 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