I have implemented segment tree in python for this
It is running in some cases and for others abort is called in build function ( I checked that by debugging in Pycharm but I couldn't understand why code is misbehaving)
Any help would be appreciated :)
The only possible reason is the input size is large, so the recursion depth exceeds the stack size resulting in runtime error. There are three solutions:-
1)Use sys.setrecursionlimit(x) to increase the stack size manually. This is a temporary fix, because x can’t be increased above certain range, and the input may be bigger.
2)Rewrite the recursive procedure in an iterative manner.
3)Use some other language like C++ or Java.
Your first approach didn’t work
Personally, I don’t think that its recursion depth causing this error because recursion depth is just log_2(100000)<18
And I don’t want to use C++/JAVA because I am learning python, I know that I will resolve C++ error on myself
And also if you will run this code on some input you will find this error
(line 46) IndexError: list assignment index out of range
@anushi I saw your code. I think the problem is in the initialization of Segment tree. Why are you only making st of only N elements ?. In segment tree the number of nodes are 4*n. So I think it will cause a problem when n = 10^5. SO I think you should initialize it with 4N