| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
According to animeshf, it is possible: his comment
But the implementation link he shared is expired so the implementation is gone! I'm confused one how to lazily propagate changes in the second dimension, more specifically how to store the lazy updates in a way so that both operations are logn^2 worst case.
Any ideas here?
Here is a way to support range sum query and range addition update. I don't know of a way to support range set update, however.
https://github.com/bqi343/USACO/blob/master/Storage/(2)%20Data%20Structures/(5)%202D%20BIT%20with%20Range%20Update.cpp
Auto comment: topic has been updated by brdy (previous revision, new revision, compare).
Here
Although the code is quite clean, would you please provide some explanation about it?
Instead of lazily propagating down values he just adds them as he goes down. If a node is not completely within or out of the range he adds the lazy values from min(end,right) to max(start,left) to avoid over-adding. This won't work for max/min though, I'm not sure if there is another idea for those.