Почему рекурсия возвращает NoneType в следующем коде дерева сегмента?

Question

Я попытался построить дерево сегментов, используя python, используя который я могу получить сумму цифр в массиве 'arr' из индекса (l, r).Я получаю ожидаемое дерево правильно, но оно показывает ошибку, когда я вызываю 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: неподдерживаемые типы операндов для +: 'NoneType' и 'int'

Answer 1

Вы не вернули сумму поддеревьев.из-за этого возвращается None.Вы должны написать так.

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