今天终于搞定线段树，写了几道题，记录其中比较典型的一道模板题：

lintcode 207 · 区间求和 II

题目很简单：

在类的构造函数中给一个整数数组, 实现两个方法 query(start, end) 和 modify(index, value):
对于 query(start, end), 返回数组中下标 start 到 end 的 和。
对于 modify(index, value),把数组中下标为 index 的数改为 value.

样例

输入:
[1,2,7,8,5]
[query(0,2),modify(0,4),query(0,1),modify(2,1),query(2,4)]
输出: [10,6,14]
说明:
给定数组 A = [1,2,7,8,5].
在query(0, 2)后, 1 + 2 + 7 = 10,
在modify(0, 4)后, 将 A[0] 修改为 4， A = [4,2,7,8,5].
在query(0, 1)后, 4 + 2 = 6.
在modify(2, 1)后, 将 A[2] 修改为 1，A = [4,2,1,8,5].
After query(2, 4), 1 + 8 + 5 = 14.

输入:
[1,2,3,4,5]
[query(0,0),query(1,2),quert(3,4)]
输出: [1,5,9]
说明:
1 = 1
2 + 3 = 5
4 + 5 = 9

解答

基本知识是递归，写法是DFS与回溯，可以说是非常经典了。

class Node:
    def __init__(self, sum=0, left=None, right=None, start=0, end=0):
        self.left = left
        self.right = right
        self.start = start
        self.end = end
        self.sum = sum

def build(array, start, end):
    if start == end:
        return Node(sum=array[start], start=start, end=start)
    mid = (start + end) // 2
    node = Node(left=build(array, start, mid), right=build(array, mid + 1, end))
    node.start = start
    node.end = end
    node.sum = node.left.sum + node.right.sum
    return node

def write(node, index, value):
    if index == node.start == node.end:
        node.sum = value
        return
    mid = (node.start + node.end) // 2
    if index <= mid:
        write(node.left, index, value)
    else:
        write(node.right, index, value)
    node.sum = node.left.sum + node.right.sum
    return

def query(node, start, end):
    if node.start >= start and node.end <= end:
        return node.sum
    mid = (node.start + node.end) // 2
    if mid < start:
        return query(node.right, start, end)
    elif mid >= end:
        return query(node.left, start, end)
    else:
        return query(node.left, start, mid) + query(node.right, mid, end)

class Solution:
    """
    @param: A: An integer array
    """

    def __init__(self, A):
        if not A:
            return
        self.root = build(A, 0, len(A) - 1)

    """
    @param: start: An integer
    @param: end: An integer
    @return: The sum from start to end
    """

    def query(self, start, end):
        return query(self.root, start, end)

    """
    @param: index: An integer
    @param: value: An integer
    @return: nothing
    """

    def modify(self, index, value):
        write(self.root, index, value)

if __name__ == '__main__':
    s = Solution([])
    s = Solution([1, 4, 2, 3])
    s.modify(1, 5)
    print(s.query(1, 3))
    print(s.query(2, 3), s.query(1, 3), s.query(0, 2), s.query(0, 3))

线段树的原理和其他实现请参考 https://www.jianshu.com/p/91f2c503e62f