Segment Tree size is too small

[bogoconic1]

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 #81

Thanks

[Mukundan314]

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]

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

cc: @cheran-senthil

[Mukundan314]

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]

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]

Thanks, will do so next time