原題

給定一個整數(shù)數(shù)組（下標由 0 到 n-1，其中 n 表示數(shù)組的規(guī)模），以及一個查詢列表。每一個查詢列表有兩個整數(shù) [start, end] 。 對于每個查詢，計算出數(shù)組中從下標 start 到 end 之間的數(shù)的總和，并返回在結果列表中。

對于數(shù)組 [1,2,7,8,5]，查詢[(1,2),(0,4),(2,4)], 返回 [9,23,20]

解題思路

• 建立下標型線段樹， 自下而上，回溯更新
• root.sum = root.left.sum + root.right.sum
• for循環(huán)query更新結果

完整代碼

"""
Definition of Interval.
class Interval(object):
    def __init__(self, start, end):
        self.start = start
        self.end = end
"""
class segmentTreeNode:
    def __init__(self, start, end, Sum):
        self.start, self.end, self.Sum = start, end, Sum
        self.left, self.right = None, None

class Solution: 
    """
    @param A, queries: Given an integer array and an Interval list
                       The ith query is [queries[i-1].start, queries[i-1].end]
    @return: The result list
    """
    def build(self, L, start, end):
        if start > end:
            return None
            
        root = segmentTreeNode(start, end, 0)
        if start != end:
            mid = (start + end) / 2
            root.left = self.build(L, start, mid)
            root.right = self.build(L, mid + 1, end)
            root.Sum = root.left.Sum + root.right.Sum
        else:
            root.Sum = L[start]
        return root
        
    def query(self, root, start, end):
        if root.start == start and root.end == end:
            return root.Sum
            
        mid = root.start + (root.end - root.start) / 2
        leftSum, rightSum = 0, 0
        if start <= mid:
            if mid < end:
                leftSum = self.query(root.left, start, mid)
            else:
                leftSum = self.query(root.left, start, end)
        if mid < end:
            if start <= mid:
                rightSum = self.query(root.right, mid + 1, end)
            else:
                rightSum = self.query(root.right, start, end)
        return leftSum + rightSum
        
    def intervalSum(self, A, queries):
        root = self.build(A, 0, len(A) - 1)
        res = []
        for q in queries:
            res.append(self.query(root, q.start, q.end))
        return res