我正在使用 this 解决 segment tree 问题，但出现时间限制错误。
下面是我的范围最小查询的原始代码，通过在我的代码中将 min 更改为 max 可以解决上述问题。我不知道如何提高代码的性能。你能帮我解决它的性能问题吗？
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
这可以迭代实现吗？
最佳答案
语言选择
首先，如果你使用 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 的效率。
关于python - Python中的段树实现，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/41085553/