线段树详解

前言

这是一篇蒟蒻的博客，可能有许多错误或不详细的地方，欢迎大佬们指出。
这篇文章主要参考了这篇博文：http://blog.csdn.net/zearot/article/details/48299459

目录

• 什么是线段树
  
  • 什么是区间加法
• 线段树的原理及实现
  
  • 储存方式
  • 初始化
  • 单点修改
  • 区间修改
    
    • 懒惰标记
      
      • 相对标记和绝对标记
      • 下传标记
  • 区间查询
  • 指针储存和动态开点
• 扩展及应用
  
  • 权值线段树
  • 可持久化线段树（主席树）
• 例题

什么是线段树

线段树，是一种二叉搜索树。它将一段区间划分为若干单位区间，每一个节点都储存着一个区间。它功能强大，支持区间求和，区间最大值，区间修改，单点修改等操作。
线段树的思想和分治思想很相像。
线段树的每一个节点都储存着一段区间[L..R]的信息，其中叶子节点的L等于R。它的大致思想是：将一段大区间平均地划分成2个小区间，每一个小区间都再平均分成2个更小区间……以此类推，直到每一个区间的L等于R（这样这个区间仅包含一个节点的信息，无法被划分）。通过对这些区间进行修改、查询，来实现对大区间的修改、查询。
这样一来，每一次修改、查询的时间复杂度都只为O(log2n)$O({\log }_{2}n)$。
但是，可以用线段树维护的问题必须满足区间加法，否则是不可能将大问题划分成子问题来解决的。

什么是区间加法

一个问题满足区间加法，仅当对于区间[L,R]的问题的答案可以由[L,M]和[M+1,R]的答案合并得到。
经典的区间加法问题有：

1. 区间求和（ΣRi=Lai=ΣMi=Lai+ΣRi=M+1ai (L≤M<R)${\mathrm{\Sigma }}_{i=L}^R{a}_i={\mathrm{\Sigma }}_{i=L}^M{a}_i+{\mathrm{\Sigma }}_{i=M+1}^R{a}_i(L\le M<R)$）
2. 区间最大值（maxRi=Lai=maxMi=Lai+maxRi=M+1ai (L≤M<R)$\underset{i=L}{\overset{R}{max}}{a}_i=\underset{i=L}{\overset{M}{max}}{a}_i+\underset{i=M+1}{\overset{R}{max}}{a}_i(L\le M<R)$）

不满足区间加法的问题有：

1. 区间的众数
2. 区间的最长不下降子序列

---

线段树的原理

注意：如果我没有特别申明的话，这里的询问全部都是区间求和
线段树主要是把一段大区间平均地划分成两段小区间进行维护，再用小区间的值来更新大区间。这样既能保证正确性，又能使时间保持在log级别（因为这棵线段树是平衡的）。也就是说，一个[L..R]的区间会被划分成[L..(L+R)/2]和[(L+R)/2+1..R]这两个小区间进行维护，直到L=R。
下图就是一棵[1..10]的线段树的分解过程（相同颜色的节点在同一层）

可以发现，这棵线段树的最大深度不超过[log2(n−1)]+2$[lo{g}_2(n-1)]+2$（其中[x]$[x]$表示对x进行下取整）
由于作者太菜，不会非递归的线段树，所以这里写的都是效率较低、较为常见的递归线段树。

储存方法

通常用的都是堆式储存法，即编号为k的节点的左儿子编号为k∗2$k\ast 2$，右儿子编号为k∗2+1$k\ast 2+1$，父节点编号为k div 2$kdiv2$，其它储存方式请见指针储存和动态开点。
通常，每一个线段树上的节点储存的都是这几个变量：区间左边界，区间右边界，区间的答案（这里为区间元素之和）
下面是线段树的定义：

struct node
{
    int l/*区间左边界*/,r/*区间右边界*/,sum/*区间元素之和*/,lazy/*懒惰标记，下文会提到*/;
    node(){l=r=sum=lazy=0;}//给每一个元素赋初值
}a[N];//N为总节点数
inline void update(int k)//更新节点k的sum
{
    a[k].sum=a[a[k].l].sum+a[a[k].r].sum;
    //很显然，一段区间的元素和等于它的子区间的元素和
}

初始化

常见的做法是遍历整棵线段树，给每一个节点赋值，注意要递归到线段树的叶节点才结束。

void build(int k/*当前节点的编号*/,int l/*当前区间的左边界*/,int r/*当前区间的右边界*/)
{
    a[k].l=l,a[k].r=r;
    if(l==r)//递归到叶节点
    {
        a[k].sum=number[l];//其中number数组为给定的初值
        return;
    }
    int mid=(l+r)/2;//计算左右子节点的边界
    build(k*2,l,mid);//递归到左儿子
    build(k*2+1,mid+1,r);//递归到右儿子
    update(k);//记得要用左右子区间的值更新该区间的值
}

单点修改

当我们要把下标为k的数字修改（加减乘除、赋值运算等）时，可以直接在根节点往下DFS。如果当前节点的左儿子包含下标为k的数（即对于左儿子区间[Llson..Rlson]$[L_{lson}..R_{lson}]$，Llson≤k≤Rrson$L_{lson}\le k\le R_{rson}$），那么就走到左儿子，否则走到右儿子（右儿子一定包含下标为k的数，因为根节点一定包含这个数，而从根节点往下走，能到达的点也一定包含这个数），直到L=R。这时就走到了只包含k的那个节点，只需要把这个点修改即可（这个点就相当于线段树中唯一只储存着k的信息的节点）。最后记得在回溯的时候把沿途经过的所有的点的值全部修改一下。

void change(int k/*当前节点的编号*/,int x/*要修改节点的编号*/,int y/*要把编号为x的数字修改成y*/)
{
    if(a[k].l==a[k].r){a[k].sum=y;return;}
    //如果当前区间只包含一个元素，那么该元素一定就是我们要修改的。
    //由于该区间的sum一定等于编号为x的数字，所以直接修改sum就可以了。
    int mid=(l+r)/2;//计算下一层子区间的左右边界
    if(x<=mid) change(k*2,x,y);//递归到左儿子
    else change(k*2+1,x,y);//递归到右儿子
}

---

区间修改

其实如果会了单点修改的话，区间修改就不会太难理解了。
区间修改大体可以分为两步：

1. 找到区间中全部都是要修改的点的线段树中的区间
2. 修改这一段区间的所有点

先来解决第一步：
我们先从根节点出发（根节点一定包含所有的点，包括被修改区间），一直往下走，直到当前区间中的元素全部都是被修改元素。
当左区间包含整个被修改区间时，我们就递归到左区间；
当右区间包含整个被修改区间时，我们就递归到右区间；
否则，情况一定就如下图所示：

怎么办？这种情况似乎有些难了。
不过，通过思考，我们可以发现，被修改区间中的元素间，两两之间都不会产生影响。
所以，我们可以把被修改区间分解成两段，使得其中的一段完全在左区间，另一端完全在右区间。
很明显，直接在mid的位置将该区间切开是最好的。如下图所示：

通过一系列的玄学操作，我们成功地把修改区间分解成一段一段的。但问题来了：我们怎样修改这些区间呢？
最暴力的做法是每一次都像建树一样，遍历区间内的所有节点，一一修改。但是这样的时间复杂度显然O(n2log2n)$O(n^{2}lo{g}_{2}n)$，比暴力O(n2)$O(n^2)$还多了个log，我要这线段树有何用？
这里就要引入一样新的神奇的东西——懒惰标记！

懒惰标记

标记的含义：本区间已经被更新过了，但是子区间却没有被更新过，被更新的信息是什么（区间求和只用记录有没有被访问过，而区间加减乘除等多种操作的问题则要记录进行的是哪一种操作）
这里再引入两个很重要的东西：相对标记和绝对标记。

---

相对标记和绝对标记

相对标记指的是可以共存的标记，且打标记的顺序与答案无关，即标记可以叠加。 比如说给一段区间中的所有数字都+a，我们就可以把标记叠加一下，比如上一次打了一个+1的标记，这一次要给这一段区间+2，那么就把+1的标记变成+3。
绝对标记是指不可以共存的标记，每一次都要先把标记下传，再给当前节点打上新的标记。这些标记不能改变次序，否则会出错。 比如说给一段区间的数字重新赋值，或是给一段区间进行多种操作。

---

有了懒惰标记这种神奇的东西，我们区间修改时就可以偷一下懒，先修改当前节点，然后直接把信息挂在节点上就可以了！
如下面这棵线段树，当我们要修改区间[1..4]，将元素赋值为1时，我们可以先找到所有的整个区间都要被修改的节点，显然是储存区间[1..3]和[4..4]的这两个节点。我们就可以先把[1..3]的sum改为3（(3−1+1)∗1=3$(3-1+1)\ast 1=3$）,把[4..4]的sum改为1（(1−1+1)∗1=1$(1-1+1)\ast 1=1$）然后给它们打上值为0的懒惰标记，然后就可以了。

这样一来，我们每一次修改区间时只要找到目标区间就可以了，不用再向下递归到叶节点。
下面是区间+x的代码：

void changeSegment(int k,int l,int r,int x)
//当前到了编号为k的节点，要把[l..r]区间中的所有元素的值+x
{
    if(a[k].l==l&&a[k].r==r)//如果找到了全部元素都要被修改的区间
    {
        a[k].sum+=(r-l+1)*x;
        //更新该区间的sum
        a[k].lazy+=x;return;
        //懒惰标记叠加
    }
    int mid=(a[k].l+a[k].r)/2;
    if(r<=mid) changeSegment(k*2,l,r,x);
    //如果被修改区间完全在左区间
    else if(l>mid) changeSegment(k*2+1,l,r,x);
    //如果被修改区间完全在右区间
    else changeSegment(k*2,l,mid,x),changeSegment(k*2+1,mid+1,r,x);
    //如果都不在，就要把修改区间分解成两块，分别往左右区间递归
    update(k);
    //记得更新点k的值
}

下传标记

碰到相对标记这种容易欺负的小朋友，我们只用打一下懒惰标记就可以了。
但是，遇到绝对标记，或是下文提到的区间查询，简单地打上懒惰标记就明显GG了。毕竟，懒惰标记只是简单地在节点挂上一个信息而已，遇到复杂的情况可是不行的啊！
于是，懒惰标记的下传操作就诞生了。
顾名思义，下传标记就是把一个节点的懒惰标记传给它的左右儿子，再把该节点的懒惰标记删去。
我们先来回顾一下标记的含义：

标记的含义：本区间已经被更新过了，但是子区间却没有被更新过，被更新的信息是什么

显然，父区间是包含子区间的，也就是对于父区间的标记和子区间是有联系的。在大多数情况下，父区间和子区间的标记是相同的。因此，我们可以由父区间的标记推算出子区间应当是什么标记。
注意：以下所说的问题都是指区间赋值，除非有什么特别的申明。
如果要给一个节点中的所有元素重新赋值为x，那么它的儿子也必定要被赋值成x。所以，我们直接在子节点处修改sum值，再把子节点的标记改变一下就可以了（由于区间赋值要用绝对标记，因此当子节点已经有标记时，要先下传子节点的标记，再下穿该节点的标记。但是区间赋值会覆盖掉子节点的值，因此在这个问题中，直接修改标记就可以了）
代码如下：

void pushdown(int k)//将点k的懒惰标记下穿
{
    if(a[k].l==a[k].r){a[k].lazy=0;return;}
    //如果节点k已经是叶节点了，没有子节点，那么标记就不用下传，直接删除就可以了
    a[k*2].sum=(a[k*2].r-a[k*2].l+1)*a[k].lazy;
    a[k*2+1].sum=(a[k*2+1].r-a[k*2+1].l+1)*a[k].lazy;
    //给k的子节点重新赋值
    a[k*2].lazy=a[k*2+1].lazy=a[k].lazy;
    //下传点k的标记
    a[k].lazy=0;//记得清空点k的标记
}

那么区间赋值就很容易解决了。我们直接修改当前节点的sum，再打上标记就可以了。在大多数问题中，我们要先下传当前节点的标记，再打上标记。但由于在这个问题的特殊性，我们就不用下传标记了。

---

区间查询

指针储存和动态开点

---

扩展及应用

权值线段树

可持久化线段树（主席树）

例题