search

stevenhalim / cpbook-code

CP4 Free Source Code Project (C++17, Java11, Python3 and OCaml)
2k stars 493 forks source link

Incorrect updating in Segment Tree? #91

Open bandgeekdante opened 3 years ago

bandgeekdante commented 3 years ago

https://github.com/stevenhalim/cpbook-code/blob/fa53432b05cdd30740032b4b4aa401b979949ff4/ch2/ourown/segmenttree_ds.cpp#L64

I think that this line should just use conquer(lsubtree,rsubtree), as currently it doesn't use the lazy value if applicable, and only checks for the minimum rather than what the conquer function specifies

bandgeekdante commented 3 years ago

Actually I think you can replace lines 62-64 with simply conquer(l(p), r(p)) since the code has already called update on both l(p) and r(p), and update always begins with propagate which ensures that the two children won't have lazy flags set.