Implementing a Segment Tree in Python

Question

I solve this problem using the segment tree but I get a temporary error. Below is my raw code for a minimum range query and by changing min to max in my code, the above problem can be solved. I do not know how I can improve the performance of my code. Can you help me with performance issues?

 t = [None] * 2 * 7 # n is length of list def build(a, v, start, end): ''' A recursive function that constructs Segment Tree for list a. v is the starting node start and end are the index of array ''' n = len(a) if start == end: t[v] = a[start] else: mid = (start + end) / 2 build(a, v * 2, start, mid) # v*2 is left child of parent v # v*2+1 is the right child of parent v build(a, v * 2 + 1, mid + 1, end) t[v] = min(t[2 * v], t[2 * v + 1]) return t print build([18, 17, 13, 19, 15, 11, 20], 1, 0, 6) inf = 10**9 + 7 def range_minimum_query(node, segx, segy, qx, qy): ''' returns the minimum number in range(qx,qy) segx and segy represent the segment index ''' if qx > segy or qy < segx: # query out of range return inf elif segx >= qx and segy <= qy: # query range inside segment range return t[node] else: return min(range_minimum_query(node * 2, segx, (segx + segy) / 2, qx, qy), range_minimum_query(node * 2 + 1, ((segx + segy) / 2) + 1, segy, qx, qy)) print range_minimum_query(1, 1, 7, 1, 3) # returns 13 

Can this be implemented iteratively?

Answer 1

Language selection

Firstly, you will probably never pass the grader if you use python. If you look at the status of all past decisions here, http://www.spoj.com/status/GSS1/start=0 , you will see that almost every decision made is written in C ++. I don't think you have a choice but to use C ++. Please note how long is 0.115s-0.230s. This is a C / C ++ only restriction. For problems that will be made in other languages, the time limit will be a round number, for example, 1 second. Python is about 2-4 times slower than C ++ in this type of environment.

Segment tree implementation problems ...?

Secondly, I'm not sure if your code really creates a tree of segments. In particular, I do not understand why this line is:

 t[v]=min(t[2*v],t[2*v+1]) 

I am sure that the node in the segment tree stores the sum of its children, so if your implementation is close to correct, I think that it should read instead

 t[v] = t[2*v] + t[2*v+1] 

If your code is “correct,” I asked how you find the maximum interval amount in the range [x_i, y_i] if you do not even store the sum of the intervals.

Iterative Segment Tree

Third, the segment tree can be implemented iteratively. Here is the C ++ tutorial: http://codeforces.com/blog/entry/18051 .

The segment tree doesn't have to be fast enough for this ...

Finally, I don’t understand how the segment tree will help you solve this problem. The segment tree allows you to query the sum of the range in log(n) . This problem requires the maximum possible amount of any range. I have not heard of a segment tree that allows a "minimum range request" or "maximum range request."

The naive solution would be O (n ^ 3) (try all n ^ 2 possible start and end points and calculate the sum in O (n) operations) for 1 query. And, if you use a segment tree, you can get the sum in O (log (n)) instead of O (n). This will only speed you up to O (n ^ 2 log (n)), which cannot work for N = 50,000.

Alternative algorithm

I think you should look at this instead, which is done in O (n) for each request: http://www.geeksforgeeks.org/largest-sum-contiguous-subarray/ . Write it in C / C ++ and be efficient with IO, as one commenter suggested.

Answer 2

You can try with generators as you can get around a lot of restrictions. However, you did not provide a dataset that clearly shows your performance problems - can you provide a problematic dataset?

Here you can try:

 t=[None]*2*7 inf=10**9+7 def build_generator(a, v, start, end): n = len(a) if start == end: t[v] = a[start] else: mid = (start + end) / 2 next(build_generator(a, v * 2, start, mid)) next(build_generator(a, v * 2 + 1, mid + 1, end)) t[v] = min(t[2 * v], t[2 * v + 1]) yield t def range_minimum_query_generator(node,segx,segy,qx,qy): if qx > segy or qy < segx: yield inf elif segx >= qx and segy <= qy: yield t[node] else: min_ = min( next(range_minimum_query_generator(node*2,segx,(segx+segy)/2,qx,qy)), next(range_minimum_query_generator(node*2+1,((segx+segy)/2)+1,segy,qx,qy)) ) yield min_ next(build_generator([18,17,13,19,15,11,20],1,0,6)) value = next(range_minimum_query_generator(1, 1, 7, 1, 3)) print(value) 

EDIT

In fact, this may not solve your problems. There is another way to overcome any limits of recursion (as described by D. Baisley in his generator tutorial - https://www.youtube.com/watch?v=D1twn9kLmYg&t=9588s around timecode 2h00)