python - Python中的线段树实现

Question

我正在尝试编写我在 Python 中学习的新数据结构，以下函数是线段树的一部分。

def query(root,interval,xy=ref_ll([False,False])):
    print interval,root
    if root.interval == interval or point(root.interval):
        return root.quadrant.reflect(root.xy * xy) #Is always gonna be of the form [a,b,c,d]
    a = q_list([0,0,0,0])
    if interval[0] < root.r.interval[0]:
        a = query(root.l,[interval[0],min(interval[1],root.l.interval[1])],root.xy * xy)
    if interval[1] > root.l.interval[1]:
        a = query(root.r,[max(interval[0],root.r.interval[0]), interval[1]],root.xy * xy)
    return a

我希望它在 O(h) 时间内运行(h 是树的高度)，但它没有，有人可以指出我犯的错误。谢谢。

编辑有关线段树的概念，请查看 http://community.topcoder.com/i/education/lca/RMQ_004.gif

函数的终止条件是区间是否为 (1,1) 的形式，即它是一个点而不是一个范围。所有的功能都实现了。 工作输入: http://pastebin.com/LuisyYCY

这是完整的代码。 http://pastebin.com/6kgtVWAq

Answer 1

可能是因为你是extending a list对于树的每一层。扩展列表的平均时间复杂度为 O(k)，其中 k 是右侧列表的大小。右侧列表的大小为 O(h)，因此平均整体时间复杂度为 O(h²)。