Как построить сегментное дерево без рекурсии?

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))?