Python中的线段树实现

Question

Python中的线段树实现

8

我正在使用线段树解决这个问题，但我得到了时间限制错误。以下是用于区间最小查询的原始代码，并通过在我的代码中更改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

这个能分步实现吗？

- sid597

你能帮我解决[代码]的性能问题吗？你想要自己解决问题的提示，还是想要分析和编码的解决方案？segments在这个问题中起什么作用？（你有阅读过segment标签的描述吗？）（提供文档字符串而获得点赞-考虑将rmq重命名以反映此上下文之外的_范围最小查询_。）我的建议：你的问题不是递归与迭代的问题。 - greybeard

@greybeard 我想要分析和编写解决方案。在添加标签时，我写了线段树，但它被拆分成了树和线段标签（对此很抱歉）。 - sid597

有人听说过优先搜索树吗？ - greybeard

1

对于任何性能问题，我建议使用Python的“thread”模块。它允许同时运行多个任务。 - Douglas

如果这被标记为segment-tree，你可能会对build()是否真的构建了一棵“区间树”产生疑问：通常在原子间隔的边界上具有明确的坐标，而不是任何有效的索引，并且集合的段重叠。您选择使end包含似乎是不寻常的，并且注释“查询范围内的线段范围”倒退了。(我不知道您的代码为什么应该超过最优解的两倍以上。) - greybeard

如果数据是同质的，这里是整数，请用array.array替换list。 - Nizam Mohamed

2个回答

2

您可以尝试使用生成器来绕过很多限制。然而，您并没有提供一个能清楚地展现您性能问题的数据集 - 您能提供一个有问题的数据集吗？

您可以在这里尝试：

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)

编辑

实际上这可能无法解决您的问题。有另一种方法可以解决递归限制的问题（正如D. Beazley在生成器教程中所述 - https://www.youtube.com/watch?v=D1twn9kLmYg&t=9588s，大约在2小时处）。

- Pierre Alex

感谢提供视频参考。真是疯狂的东西！ - Pragy Agarwal

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user2570465 · Accepted Answer

语言选择

首先，如果您使用Python，您可能永远无法通过评分器。如果您查看此处所有过去解决方案的状态http://www.spoj.com/status/GSS1/start=0，您将看到几乎每个已接受的解决方案都是用C++编写的。我认为您别无选择，只能使用C++。请注意，时间限制为0.115秒至0.230秒。这是一个“仅适用于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)中查询范围的总和。这个问题要求任何范围的最大可能总和。我没有听说过一个允许“范围最小查询”或“范围最大查询”的线段树。

一个朴素的解决方案将是O(n^3)(尝试所有n^2可能的起点和终点，并在O(n)操作中计算总和)对于1个查询。如果使用线段树，您可以在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。