Hello all
Typically lazy propagation and segment tree updates come in the form "increase range l-r by diff". What if you want to update a segment tree like "update range l-r to val". So instead of a difference, you tell it precisely what number to update to.
How would you do this? Is there an article somewhere about this?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | jiangly | 3670 |
| 3 | Kevin114514 | 3657 |
| 4 | maroonrk | 3355 |
| 5 | Um_nik | 3353 |
| 6 | squareOf105 | 3346 |
| 7 | tourist | 3343 |
| 8 | strapple | 3324 |
| 9 | heuristica | 3322 |
| 10 | jiangbowen | 3291 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 158 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | AmShZ | 143 |
| 5 | Um_nik | 141 |
| 6 | Errichto | 139 |
| 7 | adamant | 137 |
| 8 | BledDest | 134 |
| 9 | maroonrk | 133 |
| 10 | qwexd | 130 |
that's a normal segtree, i hope this help you.
In that article they are talking about adding the difference instead of changing to value.
The differences from the adding lazy propagation to the "set" lazy propagation: instead of summing the lazy of your sons, set it to the lazy node value . Instead of summing the tree[node] with the lazy node value, set the tree[node] to lazy[node]*(range) -> lazy[node]*(r-l+1). Those are the main differences, hope it helps! Here is a link to my implementation to this segment tree: https://github.com/Rockbet/Algorithms/blob/master/Data%20Structure/Segment%20Trre%20%2B%20Set%20Lazy.cpp
article
I believe changing the '+='s to '='s is enough
That won't help in lazy propogation.
it should... when updating, push down before setting new value and when querying, make sure topmost change takes preference. shouldn't this be enough?
Yes, it is enough. I dont know why he is saying it is not enough. Maybe he just doesnt know ...
it shouldn't in the classic way because you need a state of no propagation which is 0 in case of +=, in this case all numbers are valid propagation so he needs to add like a bool parameter to know if he needs to propagate or a number that can't be in the input.
just initialize the lazy with a impossible value of updating, like -123456789. Then, check if lazy[node]==-123456789, if it is, return, otherwise, update. What is the problem?