线段树

· · 个人记录

线段树

这玩意儿快烦死我了(((

这篇文章比较适合从来没学过线段树的人看，对于学过的人来说可能会有一大堆的废话一些啰嗦的地方。

当然，还是做了分类的，你可以直接 Ctrl+F 来找到你想找的东西。

建议装了 exlg 的读者在阅读时关掉 exlg，不然代码会看着有点奇怪。

线段树，顾名思义，就是线段树就是由“线段”组成的树。

前缀和可以用 O(1) 的时间去求出一个区间内所有数的和，但是区间修改的话需要 O(n) 的时间，显然是太慢了。而线段树可以将两件事的时间平衡一下。区间查询的复杂度变成了 O(\log n)，但区间修改也是 O(\log n)。

当然，线段树不仅可以用于求和，最大值最小值，区间最大连续子序列等线性的问题都可以求解。

那么讲了这么多废话线段树具体是如何实现的呢？

线段树顾名思义是一颗树，二叉树。这颗二叉树的每一个节点都对应着整个区间（这整个区间后文用数组举例）中一段小区间，如果一个节点不是叶节点，那么他的两个孩子对应的区间和起来是它对应的区间。

举个栗子（没打错字）：一个节点对应数组中的区间是 [l,r]，那么他的左孩子对应的区间应该是 [l,\frac{l+r}{2}]，右孩子对应的区间是 [\frac{l+r}{2}+1,r]。

当一个节点对应的区间中 l=r 时，说明这个区间内只有一个数了，那么这个节点就是一个叶节点，没有左孩子和右孩子了。

当然，线段树可不能光用来分割区间，每个节点还要来记录我们想要得到的答案。例如，我们想求一个区间的和，那么每个节点中就应该再记录一下对应区间的区间和；如果我们想求一个区间中的最大/最小值，那么每个节点中就应该再记录一下区间中的最大/最小值。

因为这是一颗二叉树，所以我们可以用一个数组来存储这颗二叉树，节点 u 的孩子就是节点 2u 和 2u+1。

我们可以画一个图来展示一下：

对于有 10 个数，满足 a_i=i 的数组，如果我们要求区间的和，可以构造出下面这颗二叉树（其中 u 为这个节点的编号，l 和 r 为这个节点对应数组中的区间，sum 为这段区间的和）：

关于我在画图时把 55 写成了 45 这件事。

可以发现，对于任意一个非叶子节点的节点 u，它的 sum 可以通过两个孩子的 sum 推出（最大/最小值等同理）。它的 sum 等于 2u 的 sum 加上 2u+1 的 sum。

首先先定义用来存二叉树的数组：

struct Node{
    int l,r;
    int sum;
}tr[N*4];

其中 N 是数组的长度，要开四倍的空间是应为二叉树节点编号最大会到 4N（可以用满二叉树去举个栗子）。

接下来，一个非叶子结点的节点的 sum 是需要由它的子节点推来的，我们最好写一个函数用于给这个节点赋值：

Node Merge(Node x,Node y){//x和y为u的两个孩子
    Node u;
    u.l=x.l;
    u.r=y.r;
    u.sum=x.sum+y.sum;
    return u;
    //也可以直接return {x.l,y.r,x.sum+y.sum};
}

既然是建一颗二叉树，那么必定是要用到递归的。递归的参数应该分别是一个点对应的区间（l，r）和这个点的编号（u）：

void jian(int l,int r,int u){
    //code
}

然后，递归的结束条件是什么？上面讲过，当一个点的 l=r 时，这个点便是叶节点，它也就没有孩子了，就不要递归下去了：

if(l==r){
    tr[u].l=tr[u].r=l;
    tr[u].sum=a[l];//a数组为长度为N的整个区间
    //直接写成tr[u]={l,r,a[l]};也可以
    return;
}

那么递归的内容是什么：

jian(l,(l+r)*2,u*2);
jian((l+r)*2+1,u*2+1);

显然，u 的 sum 需要由它的孩子推来：

tr[u]=Merge(tr[u*2],tr[u*2+1]);

最后我们应该怎么调用这个函数：

jian(1,N,1);

现在我们建好了这颗树，但是这颗树需要怎么使用？

我们现在知道了一些区间的和，但不是所有的。

如果查询的恰好是我们知道的一段区间，我们可以用递归直接找到它。

例如当我们需要查询的区间是 a_4 至 a_5 的和时：

但是如果线段树只能查这样的区间，那就太弱了。

因为我们知道每一个长度为 1 的区间的区间和，所以任意一个区间一定可以被拆分成许多个已知的区间。当然，我们肯定不能一个一个去查，不然复杂度又成 O(n) 了。

如图，查区间 [4,5] 时我们并没有去查区间 [4,4] 和区间 [5,5]，而是直接查的区间 [4,5]。也就是说，如果一个点对应的区间被完全的包含在了我们需要查找的这个区间内，那么我们就没有必要再去遍历它的孩子了。

举个栗子，如果我们想要查询 [3,9] 这个区间，只需要查询下图圈出的四个点即可：

这样复杂度就又变回了 O(log n)。

首先，肯定还是要用到递归，用到的参数分别是 l，r（要查询的区间，当然你把他们定义成全局的也可以）,u（当前查到的点）。

这个递归函数是需要有返回值的，返回的是要查询的区间的和。

int cha(int l,int r,int u){
    //code
}

还是先来写递归出口，如果一个节点对应的区间被完全包含在了要查找的区间中，则我们无需再继续递归下去，直接返回这一段区间的和即可：

if(l<=tr[u].l&&tr[u].r<=r)
    return tr[u].sum;

下面为了方便我们称一个节点的做孩子对应的区间为“左区间”（[tr[u].l,\frac{(tr[u].l+tr[u].r)}{2}]），右孩子对应的区间为“右区间”（[\frac{tr[u].l+tr[u].r}{2}+1,tr[u].r]）。

如果只有左区间包含了我们要查询的区间，则我们只需要递归调用左区间并返回（值）。

同理，如果只有右区间包含了我们要查询的区间，则只需要递归调用右区间并返回即可。

如果即包含了左区间的一部分，也包含了右区间的一部分（但不是完全包含），则需要分别递归调用左区间和右区间，将两次调用的返回值相加再返回。

int mid=(tr[u].l+tr[u].r)/2;
//为了代码看起来不那么繁琐，我们用mid来记录左区间与右区间的“分割线”。
if(r<=mid)return cha(l,r,u*2);
else if(l>=mid+1)return cha(l,r,u*2+1);//判断条件可以直接写成l>mid
else return cha(l,r,u*2)+cha(l,r,u*2+1);

线段树修改分“单点修改”与“区间修改”，单点修改可以算是区间修改的一种特殊情况，所以我们先来讲区间修改。

区间查询可以不用查到叶节点，但是区间修改呢？如果我们不查到叶节点，而是直接查到一个对应区间被完全包含的节点就停止，则这个节点的子节点（如果有）对应的 sum 的值就不会被修改到，就是错误的了。

但是，如果我们要一直修改，修改到叶节点，时间复杂度又变成了 O(n)，又不如前缀和了。

这时我们就需要用到懒修改了。懒修改具体是，当我们找到一个对应区间被完全包含的节点（u）时，先将这个节点的 sum 修改了，但是我们还需要多开一个数组（后面用 gai 作为这个数组的名字），用来记录这个点被修改了多少（增减了多少），例如区间中的每一个点需要加上 d，则我们先给 sum 加上 d\times 区间长度，然后将 gai_u 增加 d。

当我们在递归时（包括修改和查询时），需要将当前递归到的节点（u）修改的值“传递”给它的两个孩子。也就是 gai_{2u} 和 gai_{2u+1} 需要加上 gai_u。传递完以后呢，我们需要将 gai_u 清空，因为我们肯定不能多次去传递这个值，这样就重复计算了。

还是递归，只不过需要传的参数多了一个区间修改的值 d。

void lazy(int l,int r,int d,int u){
    //code
}

递归出口与查找的递归出口差不多，只不过需要修改一下 sum 和 gai_u。

if(l<=tr[u].l&&tr[u].r<=r){
    tr[u].sum+=d*(tr[u].r-tr[u].l+1);
    gai[u]+=d;
    return;
}

然后我们就需要将 gai_u 传递到 gai_{2u} 和 gai_{2u+1} 上，因为查询时也需要用到，所以我们将它写到一个函数里。

void Pushdown(int u){
    if(gai[u]==0)return;//为0则不用修改
    gai[u*2]+=gai[u];
    gai[u*2+1]+=gai[u];
    tr[u*2].sum+=gai[u]*(tr[u*2].r-tr[u*2+1].l+1);
    tr[u*2+1].sum+=gai[u]*(tr[u*2+1].r-tr[u*2+1].l+1);
    gai[u]=0;//不要忘记清零
}

别忘了要在函数里调用一遍 Pushdown。前面的查询里也需要在调用左节点和右节点前调用一遍 Pushdown。

后面的基本上跟查询一样，就直接写了：

int mid=(tr[u].l+tr[u].r)/2;
if(r<=mid)lazy(l,r,d,u*2);
else if(l>mid)lazy(l,r,d,u*2+1);
else{
    lazy(l,r,d,u*2);
    lazy(l,r,d,u*2+1);
}

最后在遍历完左孩子跟右孩子有，还需要更新一下自己的值。

tr[u]=Merge(tr[u*2],tr[u*2+1]);

单点修改其实就是区间修改的一种特殊的情况，即我们要修改区间 [l,r]，只不过 l=r。所以你完全可以用区间修改去做单点修改。只不过如果题目中只要求了单点修改，你可以少敲点代码。

不一步一步的写了，直接放代码把，应该都能懂：

void xiugai(int x,int d,int u){//x为单点修改的位置
    if(tr[u].l==tr[u].r&&tr[u].l==x){
        tr[u].sum+=d;
        return;
    }
    int mid=(tr[u].l+tr[u].r)/2;
    if(r<=mid)xiugai(x,d,u*2);
    else if(l>mid)xiugai(x,d,u*2+1);
    else{
        xiugai(x,d,u*2);
        xiugai(x,d,u*2+1);
    }
    tr[u]=Merge(tr[u*2],tr[u*2+1]);
}

一上是线段树的模版，我们来写一下怎么调用它们。

首先是输入数组，输入完后我们调用 jian 函数，来建树。参数传的啥前面讲过了。

然后是查询，首先需要你输入 l 和 r，然后我们只需输出 cha(l,r,1) 即可。

还有修改，区间修改是输入 l，r，d，然后调用一遍 lazy(l,r,d,u) 就可以了。

单点修改有两种方法，都是输入 x，d，如果你用的是懒修改的那种方法，则调用 lazy(x,x,d,1)。如果你用的是不用懒修改的方法，则调用 xiugai(x,d,1) 即可。

以上讲的只是线段树的模版，具体用法还要自己去练。每次写线段树时最好都是自己打一遍所有的函数，这样可以更好的记忆，赛场上就不容易出错。直接赋值粘贴有可能你漏改了什么，然后导致直接爆零（你猜为啥我会这么说）。

1.不要复制粘贴！永远不要！

2.不要忘记要开四倍的空间，包括 gai 数组。

3.Pushdown 中修改时，有的时候是 +=，有的时候要写 =，别手误啊！

完