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

- elricL

---

创建一棵树（nlogn）只需要不到2秒钟的时间。而查询n次（因此是nlogn）大约需要40多秒的时间。 - elricL

我尝试运行你的pastebin代码，弄清楚它需要输入后，出现了一个错误信息：ValueError: invalid literal for int() with 10 -- 你应该修改代码，使其能够使用与你示例树相同的数据运行。 - Ethan Furman

你的代码看起来像实现了一个区间树而不是线段树，因为你的查询是将树与一个区间进行比较而不是一个点。 - sholte

此外，您的测试用例有点令人困惑。我假设它应该是通过raw_input读取的输入，由go()函数处理，但在这种情况下，我期望它的第一行是一个单独的数字而不是一对数字，第四行（1 -1）作为间隔没有意义。如果您以代码形式而不是输入文件的形式提供测试用例，则更容易解释。 - sholte

Answer 1

可能是因为你在每个树的级别上都扩展列表。扩展列表的平均时间复杂度为O(k)，其中k是右侧列表的大小。右侧列表的大小为O(h)，因此平均总时间复杂度为O(h²)。

- user634175

---

实际上 + 号已经被重载了，不管怎样我现在已经让它更清晰了。 - elricL