[Leetcode]307. Range Sum Query

这是Leetcode第307题，给一个数组，然后求指定下标之间的数之和，已知数组中的值可以更新，并且更新和求和操作会被频繁调用。
这是一道线段树的基础题，线段树是一种二叉搜索树。它将一段区间划分为若干单位区间，每一个节点都储存着一个区间。它功能强大，支持区间求和，区间最大值，区间修改，单点修改等操作。
线段树的思想和分治思想很相像。线段树的每一个节点都储存着一段区间[L…R]的信息，其中叶子节点L=R。它的大致思想是：将一段大区间平均地划分成2个小区间，每一个小区间都再平均分成2个更小区间……以此类推，直到每一个区间的L等于R（这样这个区间仅包含一个节点的信息，无法被划分）。通过对这些区间进行修改、查询，来实现对大区间的修改、查询。
这样一来，每一次修改、查询的时间复杂度都只为\(O(log_2n)\)

注意，可以用线段树维护的问题必须满足区间加法，否则是不可能将大问题划分成子问题来解决的。

通过这道题，也可以写一个线段树的模板，如下：

#Segment tree node
class Node(object):
    def __init__(self, start, end):
        self.start = start
        self.end = end
        self.total = 0
        self.left = None
        self.right = None


class NumArray(object):
    def __init__(self, nums):
        """
        initialize your data structure here.
        :type nums: List[int]
        """
        #helper function to create the tree from input array
        def createTree(nums, l, r):

            #base case
            if l > r:
                return None

            #leaf node
            if l == r:
                n = Node(l, r)
                n.total = nums[l]
                return n

            mid = (l + r) // 2

            root = Node(l, r)

            #recursively build the Segment tree
            root.left = createTree(nums, l, mid)
            root.right = createTree(nums, mid+1, r)

            #Total stores the sum of all leaves under root
            #i.e. those elements lying between (start, end)
            root.total = root.left.total + root.right.total

            return root

        self.root = createTree(nums, 0, len(nums)-1)

    def update(self, i, val):
        """
        :type i: int
        :type val: int
        :rtype: int
        """
        #Helper function to update a value
        def updateVal(root, i, val):

            #Base case. The actual value will be updated in a leaf.
            #The total is then propogated upwards
            if root.start == root.end:
                root.total = val
                return val

            mid = (root.start + root.end) // 2

            #If the index is less than the mid, that leaf must be in the left subtree
            if i <= mid:
                updateVal(root.left, i, val)

            #Otherwise, the right subtree
            else:
                updateVal(root.right, i, val)

            #Propogate the changes after recursive call returns
            root.total = root.left.total + root.right.total

            return root.total

        return updateVal(self.root, i, val)

    def sumRange(self, i, j):
        """
        sum of elements nums[i..j], inclusive.
        :type i: int
        :type j: int
        :rtype: int
        """
        #Helper function to calculate range sum
        def rangeSum(root, i, j):

            #If the range exactly matches the root, we already have the sum
            if root.start == i and root.end == j:
                return root.total

            mid = (root.start + root.end) // 2

            #If end of the range is less than the mid, the entire interval lies
            #in the left subtree
            if j <= mid:
                return rangeSum(root.left, i, j)

            #If start of the interval is greater than mid, the entire inteval lies
            #in the right subtree
            elif i >= mid + 1:
                return rangeSum(root.right, i, j)

            #Otherwise, the interval is split. So we calculate the sum recursively,
            #by splitting the interval
            else:
                return rangeSum(root.left, i, mid) + rangeSum(root.right, mid+1, j)

        return rangeSum(self.root, i, j)

参考：
线段树详解

[Leetcode]307. Range Sum Query - Mutable

推荐阅读