Python中的段树实现

Question

我正在使用段树解决这个问题,但我得到时间限制错误.下面是我的范围最小查询的原始代码,通过在我的代码中更改,可以解决上述问题.我不知道如何提高代码的性能.你能帮我解决它的性能问题吗？minmax

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

这可以迭代实现吗？

Answer 1

语言选择

首先,如果你使用python,你可能永远不会通过评分者.如果您在这里查看所有过去解决方案的状态,http://www.spoj.com/status/GSS1/start=0,您将看到几乎每个接受的解决方案都是用C++编写的.我认为您无法选择使用C++.注意时间限制是0.115s-0.230s.这是一个"仅适用于C/C++"的时间限制.对于将接受其他语言解决方案的问题,时间限制将是一个"圆"数,如1秒.在这种类型的环境中,Python比C++慢约2-4倍.

细分树实施问题......？

其次,我不确定您的代码是否实际构建了一个分段树.具体来说,我不明白为什么这条线存在:

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

我很确定段树中的节点存储了它的子节点的总和,所以如果你的实现接近正确,我认为应该改为

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

如果你的代码是"正确的",那么[x_i, y_i]如果你甚至不存储区间总和,我会质疑如何找到范围内的最大区间和.

迭代段树

第三,可以迭代地实现分段树.这是C++中的教程:http://codeforces.com/blog/entry/18051.

段树不应该足够快......

最后,我不明白段树如何帮助您解决这个问题.段树允许您查询范围的总和log(n).此问题要求任何范围的最大可能总和.我没有听说过允许"范围最小查询"或"范围最大查询"的段树.

对于1个查询,一个朴素的解决方案将是O(n ^ 3)(尝试所有n ^ 2个可能的起点和终点并计算O(n)运算中的和).并且,如果使用分段树,则可以在O(log(n))中获得总和而不是O(n).这只能加速到O(n ^ 2 log(n)),这对N = 50000不起作用.

替代算法

我认为你应该看一下这个,每个查询运行O(n):http://www.geeksforgeeks.org/largest-sum-contiguous-subarray/.用C/C++编写,并像一位评论者建议的那样高效地使用IO.