LazySegmentTree does not work when func does not return one of its inputs
Closed this issue · 2 comments
Terryobeyes commented
Python Version:
3.7
Describe the bug
LazySegmentTree got wrong answer by query() after add()
To Reproduce
tree = LazySegmentTree([20, 300], 0, lambda a, b: a+b)
tree.add(0, 2, 1)
print(tree.query(0, 2))
>>> 321
Expected behaviour
>>> 322
Additional context
I'm just a cf specialist from Taiwan.
Mukundan314 commented
It seems that the current implementation of LazySegmentTree
does not work when func
does not return one of its inputs so functions like min
or max
will work, whereas functions like operator.mul
, operator.add
and operator.sub
won't work.
We are currently working on a new implementation to fix this.
cheran-senthil commented
Generalizing this makes it too slow, this should rather be done on a case by case basis.