cheran-senthil/PyRival

LazySegmentTree does not work when func does not return one of its inputs

Closed this issue · 2 comments

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.

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.

Generalizing this makes it too slow, this should rather be done on a case by case basis.