python - 如何在没有递归的情况下构建线段树？

Question

我试图了解使用 Python构建分段树的过程。我想出了这样的功能（有效）：

arr = [ ... ]
tree = [None] * (4*len(arr))

def build(v, vl, vr):
    if vl == vr:
        tree[v] = arr[vl]
        return

    vm = (vl + vr) // 2
    build(2*v + 1, vl, vm)
    build(2*v + 2, vm + 1, vr)
    tree[v] = tree[2*v + 1] + tree[2*v + 2]

build(0, 0, len(arr) - 1)

我怎样才能使这个构建函数迭代（无递归）？另外，以这种方式构建分段树的时间复杂度是多少？一些教程声明它是O(n)，但递归调用不是O(n*log(n))吗？

标签： pythonalgorithmrecursiontreesegment-tree