线段树

引入

顾名思义，线段树就是由一堆线段组成的树，它的每个节点都维护一段区间的信息，而叶子节点维护的则是一个点的信息。例如：

假如说我们想维护区间和的话，那么根节点就代表所有区间的和，而其它节点则代表部分区间的和。由上图我们还能发现一个性质：节点i的权值 = 左儿子的权值 + 右儿子的权值。根据这个性质，我们~~很自然地~~想到可以递归建树，我们考虑用一个结构体存储树，即：

struct tree
{
    int l, r; //左右儿子的节点
    int sum; //该店维护的信息，这里表示区间和
} tr[(maxn << 2) + 7];

void build(int i, int l, int r)
{
    if(l == r)
    {
        tr[i].sum = num[l]; //存储叶子节点的信息
        return;
    }
    int mid = (l + r) >> 1;
    build(i << 1, l, mid);
    build(i << 1 | 1, mid + 1, r); //递归建树
    tr[i].sum = tr[i << 1].sum + tr[i << 1 | 1].sum; //性质的利用
}

可能这时有人会问：为什么内存要开四倍啊？~~经验之谈~~~才不会告诉你是笔者太蒟了不会推~ 关于这点，网上有很多大佬给了详细过程，有兴趣可以去查查。

线段树的功能

我们先来看一道题

题目描述

如题，已知一个数列，你需要进行下面两种操作：

将某区间每一个数加上 $k$ 。

求出某区间每一个数的和。

输入格式

第一行包含两个整数 $n, m$ ，分别表示该数列数字的个数和操作的总个数。

第二行包含 $n$ 个用空格分隔的整数，其中第 $i$ 个数字表示数列第 $i$ 项的初始值。

接下来 $m$ 行每行包含 $3$ 或 $4$ 个整数，表示一个操作，具体如下：

1 x y k：将区间 $[x, y]$ 内每个数加上 $k$ 。

2 x y：输出区间 $[x, y]$ 内每个数的和。

输出格式

输出包含若干行整数，即为所有操作 2 的结果。

样例 #1

样例输入 #1
1
2
3
4
5
6
7
5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4
样例输出 #1
1
2
3
>11
>8
>20

对于这道题，如果我们使用朴素的方法的话，每次操作的时间复杂度为 $O(n)$ ，而总共有 $m$ 次操作，所以总的时间复杂度为 $O(nm)$ 。对于这么简单的操作，这个复杂度我们显然是不能接受的，而如果能将每次操作的复杂度降低到 $O(logn)$ ，这下子速度就比较可观了。于是，~~线段树，启动！~~

区间修改

既然我们想降低复杂度，那么我们肯定不能枚举区间的每个值进行修改，而是对整个区间进行修改，而我们的线段树正好维护区间和，于是，如果线段树的一个节点维护的区间正好在目标区间里面，我们就可以直接修改这个区间，即tr[i].sum = k * (tr[i].r - tr[i].l + 1)，意思就是将区间内每一个数加 $k$ 。

那么如果这个节点所维护的区间不完全包含在目标区间里面呢？这时候我们遍可以缩小节点维护的区间范围，即递归这个节点的左右子树，于是乎，我们得到了区间修改的规则：

如果节点维护的区间完全包含在目标区间中，则修改该节点的 $sum$
如果该节点的左子树与目标节点有交集，则搜索左子树
如果该节点的右子树与目标节点有交集，则搜索右子树

代码也不难实现啦：

void update(int i, int l, int r, int k)
{
    if(tr[i].l >= l && tr[i].r <= r) //完全包含
    {
        tr[i].sum = k * (tr[i].r - tr[i].l + 1); //修改区间维护的值
        return;
    }
    
    if(tr[i << 1].r >= l) // 左子树有交集
        update(i << 1, l, r, k);
    if(tr[i << 1 | 1].l <= r) //右子树有交集
        update(i << 1 | 1, l, r, k);
    tr[i].sum = tr[i << 1].sum + tr[i << 1 | 1].sum //别忘了更新父节点
}

这个时候可能有人要问了：为什么这样子的操作复杂度是 $log$ 级别的呢？有能力的读者可以自行思考，这个问题呢我们最后再解释。~别急~

区间查询

对于区间查询，其实跟区间修改的规则差不多，如果节点的区间完全包含在目标区间里，就返回该区间的值，如果左子树有交集就搜索左子树，右子树有……诶等会儿，我们刚刚在修改区间的时候，一个区间被修改了，它的子区间并不会被修改，那如果我们查询到它的子区间了，岂不是查询到了修改前的结果？这代表我们之前美妙的想法失败了？这可不行，我们要想办法补救一下。

试想一下，假如我们在查询子树的时候，提前知道了这个区间被修改了，不就可以了吗。所以，我们在修改一个区间的时候，可以给它打一个标记，代表这个区间修改的值，在查询其子树的时候，再把这个标记带给子树，以便下一次查询就ok啦！这个标记也是线段树的精髓，其名为懒惰标记 $(lazytag)$

代码也很简单啦：

int query(int i, int l, int r)
{
    if(tr[i].l >= l && tr[i].r <= r)
        return;
    pushdown(i); //把懒标记放给子树，方便下次查询
    
    int s = 0; //记录结果
    if(tr[i << 1].r >= l) 
        s += query(i << 1, l, r);
    if(tr[i << 1 | 1].l <= r)
        s += query(i << 1 | 1, l, r);
    return s;
}

懒标记下放

现在我们的核心问题就是如何把懒标记放给子树，其实也很简单，因为我们的操作都是递归的，所以我们只需要让子树的状态与当前状态一致即可，而我们现在的状态是什么呢，就是懒标记存放着数，且所维护的值被修改。所以，我们只需要让子树的懒标记也存放数，且修改其维护的值即可。

代码如下：

void pushdown(int i)
{
    tr[i << 1].sum = tr[i].lazy * (tr[i << 1].r - tr[i << 1].l + 1);
    tr[i << 1 | 1].sum = tr[i].lazy * (tr[i << 1 | 1].r - tr[i << 1 | 1].l + 1); //修改子树的值
    
    tr[i << 1].lazy += tr[i].lazy;
    tr[i << 1 | 1].lazy += tr[i].lazy; //修改懒标记的值
    
    tr[i].lazy = 0; //懒标记归零，防止多次修改
}

现在我们就可以实现一棵完整的线段树啦，撒花撒花

复杂度分析

最后的最后，我们还是要解决开始的问题，为什么线段树每次的操作一定是 $O(logn)$ 呢？不难发现我们时间的花费都在递归步上，我们现在来分析递归步的时间复杂度。假设当前节点为 $i$ ，查询区间为 $l, \ r$ ，于是可以分为以下情况：

l <= tr[i].l <= tr[i].r <= r 此时直接返回，不会再递归
tr[i].l <= l <= tr[i].r <= r 或者 l <= tr[i].l <= r <= tr[i].r 此时虽然会递归左右子树，但是其中一棵递归一次后就会变为情况一，所以实际上只有一棵子树会继续递归
tr[i].l <= l <= r <= tr[i].r 这里又分两种情况：
- l <= r <= mid 或者 mid <= l <= r 这种情况有一棵子树与目标区间没有交集，不会再产生递归
- l <= mid <= r 这种情况会递归产生两棵子树，且都会继续参与递归