为什么在segment Tree下面的代码中递归返回的是NoneType？

Question

我尝试使用 python 构建线段树，使用它我可以从索引 (l,r) 获取数组 'arr' 中的数字总和。我得到的预期树是正确的，但是当我调用 getSum() 时它显示错误。

from math import ceil,log2
def build(arr,tree,node,start,end):
    if start==end:
        tree[node] = arr[start]
        return tree[node];
    mid = (start+end)//2
    tree[node] = build(arr,tree,2*node + 1,start, mid) + build(arr,tree,2*node + 2,mid+1, end)
    return tree[node]
def getSum(tree,node,start,end,l,r):
    if(r<start or l>end):
        return 0
    elif r>=end and l<=start:
        return tree[node]
    else:
        mid = (start+end)//2
#         print(getSum(tree,2*node + 1,start,mid,l,r))
#         print(getSum(tree,2*node+2,mid+1,end,l,r))
        getSum(tree,2*node + 1,start,mid,l,r) + getSum(tree,2*node+2,mid+1,end,l,r)
if __name__=='__main__':
    tree = [0]*((2)**(ceil(log2(5))+1)-1)
    build([1,2,3,4,5],tree,0,0,4)
    getSum(tree,0,0,4,1,3)

error : unsupported operand type(s) for +: 'NoneType' and 'int'

Answer 1

您没有return子树的总和。因为它是 returning None。你应该这样写。

    return getSum(tree,2*node + 1,start,mid,l,r) + getSum(tree,2*node+2,mid+1,end,l,r)

为什么在segment Tree下面的代码中递归返回的是NoneType？

Why is the recursion returning NoneType in the following code of segment Tree?

data-structures

tree

segment

recursive-datastructures

segment-tree