Segment Tree（线段树）

线段树是一种用来查询搜索区间范围内数组元素的和或者最大最小值的数据结构，因为查询，搜索的时间都是O(lgn)，所以相对来说是非常高效的数据结构，但是对一个空间为O(n)的数组建构线段树需要的空间是数组的两倍（粗略估值），所以空间方面的表现会相对差一些，有一种能达到相同时间复杂度但空间占用只有O(n)的查询树Binary Indexed Tree跟线段树的表现是一样的，但是逻辑实现方面会复杂一些，下面是利用数组来实现的求区间和的线段树代码（直接把leetcode原题搬过来了）

LeetCode原题地址：Range Sum Query - Mutable

class NumArray(object):
    def __init__(self, nums):
        """
        :type nums: List[int]
        """
        if num:
            self.nums = nums
            self.n = len(nums)
            self.store = [0] * (2 ** int(2 * math.ceil(math.log(self.n, 2))) - 1)
            self.construct(0, self.n - 1, 0)

    def construct(self, start, end, index):
        if start == end:
            self.store[index] = self.nums[start]
            return self.store[index]

        mid = start + (end - start) / 2
        self.store[index] = self.construct(start, mid, 2 * index + 1) + \
                            self.construct(mid + 1, end, 2 * index + 2)

        return self.store[index]

    def update(self, i, val):
        """
        :type i: int
        :type val: int
        :rtype: void
        """
        if i >= self.n and i < 0:
            return 

        diff = val - self.nums[i]
        self.nums[i] = val
        self.updateHelp(i, 0, self.n - 1, diff, 0)

    def updateHelp(self, i, start, end, diff, index):
        if start == end:
            self.store[index] += diff
            return 

        mid = start + (end - start) / 2
        self.store[index] += diff
        if i <= mid:
            self.updateHelp(i, start, mid, diff, 2 * index + 1)
        else:
            self.updateHelp(i, mid + 1, end, diff, 2 * index + 2)

    def sumRange(self, i, j):
        """
        :type i: int
        :type j: int
        :rtype: int
        """
        return self.sumRangeHelp(i, j, 0, self.n - 1, 0)

    def sumRangeHelp(self, qs, qe, start, end, index):
        if qs > end or qe < start:
            return 0
        if qs <= start and qe >= end:
            return self.store[index]
        mid = start + (end - start) / 2
        return self.sumRangeHelp(qs, qe, start, mid, 2 * index + 1) + \
                self.sumRangeHelp(qs, qe, mid + 1, end, 2 * index + 2)


# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# obj.update(i,val)
# param_2 = obj.sumRange(i,j)