线段树用于动态的区间更新和查询（区间最大值、最小值、加和、最大公约数、最小公倍数等）

各节点除了保存下标区间，还应保存该区间对应的聚合值。叶节点对应单点区间，内节点对应虚拟的合并区间。若某内节点表示区间[i..j]，那左子节点表示区间[i..(i+j)/2]，右子节点表示区间[(i+j)/2+1..j]。

数组实现

用n个叶节点保存n个数组元素，还需要n-1个内节点。类似堆的数组实现，数组大小2n，不用tree[0]，叶节点从n开始。父子关系：p=i/2、lchild=2*i、rchild=2*i+1。每个叶节点（i>=n）表示区间nums[i..i]，每个内节点（i<n）表示左子节点和右子节点的合并区间。各节点表示的区间是固定的，节点中不再显式记录，只记录聚合值。三个操作：构建、更新、查询。

class SegmentTree {
    int _n;
    vector<int> _tree;
public:
    SegmentTree(const vector<int> &nums) 
        : _n(nums.size()), _tree(2 * _n) {
        build(nums); 
    }
    
    void build(const vector<int> &nums) {
        // 叶节点是原数组元素
        for (int i = _n; i < 2 * _n; i++) {
            _tree[i] = nums[i-_n];
        }
        // 内节点计算聚合信息
        for (int i = _n - 1; i >= 1; i--) {
            _tree[i] = _tree[2*i] + _tree[2*i+1];
        }
    }
    
    void update(int i, int val) {
        i += _n;
        _tree[i] = val;
        for (int j = i/2; j >= 1; j /= 2) {
            _tree[j] = _tree[2*j] + _tree[2*j+1];
        }
    }

    // 返回nums[i..j]的和
    int query(int i, int j) {
        int sum = 0;
        for (i += _n, j += _n; i <= j; i /= 2, j /= 2) {
            if (i % 2 == 1) sum += _tree[i++];
            if (j % 2 == 0) sum += _tree[j--];
        }
        return sum;
    }
};

query()的解释见http://codeforces.com/blog/entry/18051

General idea is the following. If l, the left interval border, is odd (which is equivalent to l&1) then l is the right child of its parent. Then our interval includes node l but doesn't include it's parent. So we add t[l] and move to the right of l's parent by setting l = (l + 1) / 2. If l is even, it is the left child, and the interval includes its parent as well (unless the right border interferes), so we just move to it by setting l = l / 2. Similar argumentation is applied to the right border. We stop once borders meet.

递归实现

递归树实现
递归数组实现

每个treeIdx对应范围[lo,hi]，lo==hi是叶节点，build、query、update都是用后序遍历merge两子树解。因为只用递归向下计算子节点，不用计算父节点，可以使用tree[0]，子节点变为：lchild=2*i+1、rchild=2*i+2。因为递归到叶节点结束，算空节点凑成完全二叉树，最多4n个节点（叶节点n，最底层空叶节点最多n，全部叶节点最多2n，全部节点最多4n）。

正常线段树一次更新一个元素，并把更新沿着"祖父=>叶"的路径传播。要想一次更新一个范围，用lazy propagation技术，意为：对子节点的更新延迟处理，先记录到与tree[]同样大小的lazy[]数组中。更新时先应用本节点的lazy[i]更新（并把本该传播给子节点的更新记录到lazy[lchild]、lazy[rchild]，lazy[i]清零），再应用本次更新调用的更新（并把本该传播给子节点的更新记录到lazy[lchild]、lazy[rchild]）；查询时，先应用本节点的lazy[i]更新（并把本该传播给子节点的更新记录到lazy[lchild]、lazy[rchild]，lazy[i]清零），然后递归查询。