线段树

概念

线段树是用来维护 区间信息 的数据结构，可以在 O（logN）的时间复杂度实现单点修改、区间修改、区域查询（区域求和，求区间最大值、求区间最小值等操作）。

基本结构与建树

线段树将每个长度不为1的区间划分成左右两个区间递归求解，把整个线段划分成一个树形结构，通过合并左右区间信息来求得该区间的信息。
接下来，通过一个例子来展示线段树的建立、区间和、区间修改等操作。
给定一个数组，如下图。

注：这里下标为0 的元素为了填位的，我们需要让数组中第一个有意义的数字从下标1开始。

我们可以看一下线段树的形状，如下图所示。

线段树 根节点 的下标为1，保存着 nums[1] + nums[2] + nums[3] + nums[4] + nums[5] 的信息。
假设 为线段树的非叶子节点，的左儿子节点为 ，的右儿子节点为 。

如果 表示的是区间 （即 ），
那么 的左儿子节点表示的是区间 ，的右儿子节点表示的是区间 。
注：线段树的空间为 4n。
下面是创建线段树的具体代码：

//建立线段树
void buildSegementTree(int[] nums, int s, int t, int p){
    //对区间[s, t]建立线段树，当前节点为p
    //s的初始值为1，t的初始值为 nums中最后一个元素的下标
    //如果当前区间只剩一个节点，则不再往下划分，即当前节点设置为叶节点并返回
    if(s == t){
        tree[p] = nums[t];
        return;
    }
    int m = s + ((t - s) >> 1);
    //递归建立左右子树
    buildSegementTree(nums, s, m, 2 * p);
    buildSegementTree(nums, m+1, t, 2 * p + 1);
    //根据上面创建好的左右孩子节点，计算当前节点p的值
    tree[p] = tree[2 * p] + tree[2 * p + 1];
}

区间和查询

给定区间 ，求该区间的和，即 。
如果查询区间 ，直接返回 tree[1] 即可。如下图。

但是，如果要查询区间 ，应该如何处理？
从上面的图中可以看出，区间 包含了多个线段树的节点，因此，我们可以将问题转变为查询区间 和 。如下图所示。

如何实现这一过程呢？
在给定查询区间 [l, r] 的前提下，我们维护一个区间 [s, t]，和存储当前区间和的节点 p。
如何判断 区间 [s, t] 是否与 [l, r] 有交集？
详细内容看下面的代码注释：

//给定区间[l, r],求该区间的和
//[s, t]为当前节点包含的区间，p为当前节点的编号
int getSum(int l, int r, int s, int t, int p){
    //当前区间为查询区间的子集时直接返回当前区间的和
    //这里可以分为两种情况：
    //第一种:[l,r] 等于 [s,t],直接返回
    //第二种:[s,t] 属于 [l, r],这种情况是发生在递归查询过程中
    //        比如查询[3,5]，在递归查询时会扫描到区间[3,3]，那么
    //      区间[3,3]也是答案的组成部分之一，所有也要返回
    if(l <= s && t <= r) {
        return tree[p];
    }

    int m = s + ((t - s) >> 1);

    int sum = 0;

    //判断左孩子的区间[s, m]是否与[l,r]有交集
    //如果左孩子的右边界m >= 查询区间的左边界 l
    //就证明它们有交集，即左孩子中有一部分内容包含在查询区间[l,r]中
    //否则的话，则两个没交集，也就不用访问左孩子了
    if(l <= m) {
        sum += getSum(l, r, s, m, 2 * p);
    }

    //判断右孩子的区间[m+1,t]是否与[l,r]有交集
    //如果右孩子的左边界m+1 <= 查询区间的右边界r
    if(r > m) {
        sum += getSum(l, r, m+1, t, 2 * p + 1);
    }
    return sum;
}

对于区间 [3, 5] 的查询过程，我们给出如下流程图。图中画出在查询过程中访问到的区间，至于那些没访问到的区间，就省略了。先判断当前区间是否为查询区间的子集，如果是的话，直接返回。接下来去左右子树中寻找是否存在与查询区间有交集的区间，做累加，最后返回结果。

区间修改和懒惰标记

如果要求修改区间 [l, r]，把所有包含在区间 [l, r] 中的节点都遍历一遍、修改一次，时间复杂度无法承受。因此，在这里引入 懒惰标记。
懒惰标记，就是通过延迟对节点信息的修改，从而减少可能不必要的操作次数。每次执行修改时，我们通过打标记的方法表明对该节点对应的区间在某一次操作中被更改，但不更新该节点的子节点信息。实质性的修改 则在下一次访问带有标记的节点时才进行。
主要思想：第一个，想修改区间必须先找到区间，这个跟求区间和是一样的（判断当前访问的区间与查询区间是否有交集）。第二，找到区间后，更新当前区间的值并打上标记，我们不对当前区间的子区间进行递归更改，但是我们要从当前区间 自下而上 地更改节点的值。
接下来，我们用一个例子来展示这一过程。
对区间 [3, 5] 中的所有数加上 5。
如图所示，左边的为未进行修改的线段树，右边为区间对应的懒惰标记。

我们寻找到区间 [3, 3]，更新当前节点的值，并设置懒惰标记。
因为区间遍历的过程是自下而上的，所以会在这一过程中更新区间 [3, 3] 的父节点的值，即区间[1, 3]。（这一个过程中被更新的父节点，不需要进行懒惰标记）

紧接着，寻找到区间 [4, 5]，同样，只更新区间[4, 5] 的值 和其对应的懒惰标记，不对子区间进行更新。但是，在这里，我们要考虑一个问题，一个非叶子节点所对应的区间包含的元素个数不一定只有1个或两个，所以我们要计算当前区间 [s, t] 内包含的元素个数，即 元素个数 = t - s +1。因为在线段树中的一个节点存储着一段区间对应的区间和，所有更新的值为 更新变量 * 区间内元素个数。
（为什么在区间 [3, 3] 中没有这样的计算，因为区间[3,3] 是叶子节点，可以不考虑这些因素）。

接着，随着递归的逐层返回（自下而上），更新根节点的值。

其实在这里还会引出一个问题，就是我们应该在什么时候对那些拥有懒惰标记的子节点进行更新。答案是：在计算区间和区间修改的时候进行更新。
这里可能会有些疑惑：不是说在进行区间修改时不更新子区间吗？这个只能说是在当前区间修改时不进行更新，但是如果存在多次修改，第一次不进行更新，第二次如果访问到在
第一次被懒惰标记的区间，还是要进行修改的~~~。
区间修改代码：

//[l,r] 为修改区间，c为被修改的元素变化量
//[s,t] 为当前节点包含的区间，p为当前节点的编号
void update(int l, int r, int c, int s, int t, int p) {
    //当前区间为修改区间的子集时直接修改当前节点的值，
    //然后打标记，结束修改
    if(l <= s && t <= r) {
        tree[p] += (t - s + 1) * c;
        lazy[p] += c;
        return;
    }

    int m = s + ((t - s) >> 1);

    //如果当前节点的懒惰标记非空，则更新当前节点的两个子节点的值和懒惰标记值
    //其实s!=t 是用于那些被标记的叶子节点，因为它们本身就没有子节点了，
    //所以不需要往下进行修改
    if(lazy[p] != 0 && s != t){
        //计算区间[s,m]包含的元素个数
        tree[2 * p] += lazy[p] * (m - s + 1);
        //计算区间[m+1,t]包含的元素个数
        tree[2 * p + 1] += lazy[p] * (t - m);

        //将标记下传给子节点
        lazy[2 * p] += lazy[p];
        lazy[2 * p + 1] += lazy[p];

        //清空当前节点的标记
        lazy[p] = 0;
    }

    //这也是找区间的过程
    if(l <= m) {
        update(l, r, c, s, m, 2 * p);
    }
    if(r > m) {
        update(l, r, c, m+1, t, 2 * p + 1);   
    }

    //自下而上更新父节点的值
    tree[p] = tree[2 * p] + tree[2 * p + 1];
}

如果加入了 `懒惰标记` 的话，那么区间求和也要进行相应的标记检查和下传。<br />`区间求和代码`：

//给定区间[l, r],求该区间的和
//[s, t]为当前节点包含的区间，p为当前节点的编号
int getSum(int l, int r, int s, int t, int p){
    //当前区间为查询区间的子集时直接返回当前区间的和
    //这里可以分为两种情况：
    //第一种:[l,r] 等于 [s,t],直接返回
    //第二种:[s,t] 属于 [l, r],这种情况是发生在递归查询过程中
    //        比如查询[3,5]，在递归查询时会扫描到区间[3,3]，那么
    //      区间[3,3]也是答案的组成部分之一，所有也要返回
    if(l <= s && t <= r) {
        return tree[p];
    }

    int m = s + ((t - s) >> 1);

    //在这里进行标记检查和下传
    if(lazy[p] != 0 && s != t){
        //计算区间[s,m]包含的元素个数
        tree[2 * p] += lazy[p] * (m - s + 1);
        //计算区间[m+1,t]包含的元素个数
        tree[2 * p + 1] += lazy[p] * (t - m);

        //将标记下传给子节点
        lazy[2 * p] += lazy[p];
        lazy[2 * p + 1] += lazy[p];

        //清空当前节点的标记
        lazy[p] = 0;
    }


    int sum = 0;

    //判断左孩子的区间[s, m]是否与[l,r]有交集
    //如果左孩子的右边界m >= 查询区间的左边界 l
    //就证明它们有交集，即左孩子中有一部分内容包含在查询区间[l,r]中
    //否则的话，则两个没交集，也就不用访问左孩子了
    if(l <= m) {
        sum += getSum(l, r, s, m, 2 * p);
    }

    //判断右孩子的区间[m+1,t]是否与[l,r]有交集
    //如果右孩子的左边界m+1 <= 查询区间的右边界r
    if(r > m) {
        sum += getSum(l, r, m+1, t, 2 * p + 1);
    }
    return sum;
}