Segment tree implementation in Python

Question

I am solving this problem using segment tree but I get time limit error. Below is my raw code for range minimum query and by changing min to max in my code the above problem can be solved . I don't know how I can improve the performance of my code. Can you help me with its 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

Choice of Language

First, you probably will never pass the grader if you use python. If you look at the status of all past solutions here, http://www.spoj.com/status/GSS1/start=0 , you will see that every almost every accepted solution has been written in C++. I do not think you have a choice but to use C++. Notice how the time limit is 0.115s-0.230s. That's an "only-for-C/C++" time limit. For problems that will accept solutions in other languages, the time limit will be a "round" number like 1 second. Python is about 2-4x slower than C++ in this type of environment.

Segment Tree Implementation Issues...?

Second, I'm not sure if your code is actually constructing a segment tree. Specifically, I don't understand why this line is there:

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

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

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

If your code is "correct", then I would question how you are finding the maximum interval sum within the range [x_i, y_i] if you don't even store the interval sums.

Iterative Segment Tree

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

Segment tree isn't supposed to be fast enough for this...

Finally, I don't understand how a segment tree is going to help you for this problem. A segment tree lets you query the sum of a range in log(n). This problem asks for the maximum possible sum of any range. I have not heard of a segment tree that allows for "range minimum query" or "range maximum query."

A naive solution will be O(n^3) (try all n^2 possible start and end points and compute 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). That only speeds you up to O(n^2 log(n)), which cannot work for N = 50000.

Alternative algorithm

I think you should be looking at this instead, which runs in O(n) per query: 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 give a try with generators as you can go around a lot of limitations. However you did not provide a dataset which shows your performances issues clearly - 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 that may not fix your issues. There is another way to workaround any recursion limits (as described by D. Beazley in its tutorial on generators - https://www.youtube.com/watch?v=D1twn9kLmYg&t=9588s around the timecode 2h00)