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

# | User | Rating |
---|---|---|

1 | tourist | 3707 |

2 | Benq | 3672 |

3 | ksun48 | 3575 |

4 | Radewoosh | 3562 |

5 | Miracle03 | 3480 |

6 | maroonrk | 3406 |

7 | ecnerwala | 3400 |

8 | peehs_moorhsum | 3384 |

9 | sunset | 3338 |

10 | Um_nik | 3320 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 208 |

2 | YouKn0wWho | 201 |

3 | Um_nik | 197 |

4 | Errichto | 181 |

4 | sus | 181 |

6 | awoo | 179 |

7 | tourist | 175 |

8 | -is-this-fft- | 171 |

8 | SecondThread | 171 |

10 | Ashishgup | 170 |

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

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/27/2021 17:32:28 (g2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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.

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

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

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

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.

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?

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.

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

And a simple linear version, without context: http://pastebin.com/CuuRyRZw

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