search

cheran-senthil / PyRival

⚡ Competitive Programming Library
https://pyrival.readthedocs.io/
Apache License 2.0
1.17k stars 312 forks source link

Segment Tree size is too small #82

Open bogoconic1 opened 1 year ago

bogoconic1 commented 1 year ago

Describe the bug Copied LazySegmentTree.py template to solve this problem, but when submitting gave Runtime Error On Test 5 https://codeforces.com/contest/1549/submission/186542539

After debugging, realised that size of self._lazy and self._data is too small. Changed it from 2_size to 4_size and the code ACs https://codeforces.com/contest/1549/submission/186543644

Expected behaviour Should not throw an index out of bounds error

Additional context Submitted a pull request for this issue https://github.com/cheran-senthil/PyRival/pull/81

Thanks

Mukundan314 commented 1 year ago

Specific testcase your code fails for is:

2
1 2

In this testcase your code queries the segment tree for [1, 1) which is an empty range, both SegmentTree and LazySegmentTree don't support empty ranges.

Mukundan314 commented 1 year ago

We can probably update SegmentTree and LazySegmentTree to return default for empty ranges.

cc: @cheran-senthil

Mukundan314 commented 1 year ago

Actually it seems I was a bit mistaken its seems that SegmentTree and LazySegmentTree do support empty ranges. Its that your codes queries outside the range of the array.

bjorn-martinsson commented 1 year ago

The issue is that if len (the variable self._len) is a power of 2, then query(len, len) or query(len, len, value) will fail.

This is arguably not a bug, but it is a werid edge case. The reason why the functions query(start, end) and add(start, end, value) get index out of bound is that the starting value start is assumed to be in the range [0,self._len). If we want both functions to support empty ranges, I think that a good fix would be to put an if check for start == stop (or start >= stop if we want to be 100% consistent with the other pyrival segment tree implementations) in the beginning of both query and add.

Btw @bogoconic1, it is a lot easier to debug something if you post a runable python script that triggers the bug instead of linking to a codeforces submission. Please try to do so in the future =)

bogoconic1 commented 1 year ago

Thanks, will do so next time