线段树

首先，如果你在这之前不知道线段树的话，那么希望我的文章对你有帮助；

如果您已经会了，那么请移步，这里只介绍线段树最基本的概念；

引入

~先来看引入：

给定一个整数序列，每次操作会修改序列上某个位置的数，或者是询问序列中某个区间内的所有数和。

如果我们采取暴力的话，那么单点修改的复杂度为O(1);

但是询问区间和的单次复杂度为O（n）（假设区间长度为n的话）

如果我们用前缀和的话，会发现询问区间和以及单点修改的复杂度与暴力相反；

也就是说，假设我们询问次数为m的话

那么总共的复杂度就是O（mn）而n和m一般是10^5级别的；

所以两种算法都失效；

上述这个例子同时也是树状数组的引例（树状能干的线段树基本能干）

~再来看一个例子

给定一个长度为n的序列ai，有m次操作，

操作一共分为3种：
操作1.把某个数加上x；
操作2.询问一段区间中的最大/小值。
操作3.询问一段区间的和。
数据范围：1<=n,m<=200000,|ai|<=10的9次方,|x|<= 10的9次方 ，时限1s

对于最大/最小值，很多人可能会想到树状数组+差分（如果不知道树状数组也没关系）

但是对于这题来说已经不适用了，怎么办呢？

概念

那么我们进入正题，一个更通用的数据结构——线段树！

线段树其实是一颗二叉树，树上每个节点对应序列上的一段区间；

它类似于树状数组，也是利用分治的思想，把区间操作转移到二叉树上进行的一种数据结构。

它和树状数组有共同点，也有不同之处。
每个节点记录一些必要的信息，比如说区间和、最值。

如上图所示

• 我们会发现假设一个序列长度为n；
• 根节点对应的是整个区间[1,n]；
• 假设一个节点所代表的区间为[l,r]
• 当l==r时，很明显这个节点就是叶节点（看图）；
• 否则它一定有两个孩子，记mid=（l+r）>>1(就是l+r/2）；
• 会发现左孩子代表的区间是（l,mid）,而右孩子所代表的为（mid+1,r）；
• 另外，我们也可以看出线段树中所有的节点数是n+n/2+n/4+……+1=2n-1(一层层往上数）
• 并且假设线段树高度为h，那么很显然h只有（logn）级别；
• 假设我们维护的序列长度不是如图所示的10，而是2的整数次幂的话，线段树必定是一棵满二叉树；
• 其他情况的话，线段树前h-1层是满二叉树，最后一层有可能不满。（也就是二叉树的性质）

应用

线段树初始化

给定一个序列a0一直到an-1，接下来有m次操作，其中有两种操作，给定i，x将ai修改为x，或是给定l，r求序列[l,r]的最小值（一本通例1）

（注：图不是上面那一张）

我们会发现树上的每一个点维护了它所对应的的区间最小值，我们可以通过递归来得到这棵线段树，用build（k,l,r）来构建区间为（l，r）的线段树

k是这个区间的标号（也就是节点的编号）

如果l==r我们会发现它就是一个叶节点，所以直接把最小值设成自己就可以了

否则，我们新建一个节点，接下来递归得到它的两个孩子（k*2,l,mid）以及（k*2+1，mid+1，r）;

而它的最小值其实也就是它的两个孩子的较小的那一个

因为初始化线段树只需要访问所有结点一次，所以它的复杂度与结点个数同阶O（n）

此外要注意线段树的数组要开到4*n而不是2*n，虽然结点个数是2n-1，可实际上最后一层产生了空余，所以保存线段树的数组长度要不超过4n才不会越界（具体可以手画一下）

我们来看一下初始建线段树的具体代码实现

void build(ll k,ll l,ll r) { if(l==r) { m[k]=a[l]; return ; }//如果是叶节点，最小值为本身 ll mid=l+r>>1; build(k<<1, l, mid); build(k<<1|1, mid+1, r); m[k]=min(m[k<<1],m[k<<1|1]);//m[k*2],m[k*2+1] }

询问区间

接下来是区间的询问

我们会发现较靠近上方的节点对应较大的区间，通过节点就能知道大部分值的最小值；

我们可以通过证明发现，需要访问的节点个数是O（logn）级别的（后续更新）

当一开始访问根节点，接下来的访问节点对应区间与询问的区间，我们会发现它们间的关系仅有三种：
1.当前区间和询问区间完全没有交集，那么我们就完全不需要再次递归了（因为越靠上面区间范围越大，既然已经没有交集，孩子更不可能有交集），除此之外我们可以返回一个不影响结果的最大值；

2.如果当前的询问区间是包含当前区间，那么直接返回当前区间维护好的最小值（之前已经维护无需递归）

3.以上都不是，那么两个孩子递归处理，返回两个结果里的最小值；

以上就是全部思路了，代码实现：

ll query(ll k,ll l,ll r,ll x,ll y) { if(l>y||r<x) return 2147483647;//没有任何交集，返回一个极大值 if(l>=x&&r<=y) return m[k];//维护最小值，不需要递归 ll mid=l+r>>1; return min(query(k<<1, l, mid, x, y),query(k<<1|1, mid+1, r, x, y));否则递归两个孩子取min }

单点修改操作

我们会发现对于一个结点ai如果要修改更新它，那么包含这个i位置的结点的值都需重新计算。

假设我们修改的值是v那么我们可以通过递归来实现这一操作

1.当递归到叶节点时，同上面的思路，叶节点自身修改即可；

2.否则当前最多只有一个孩子包含位置i，继续递归修改，然后将当前结点代表的区间最小值也更新一下

我们会发现因为线段树的层数是O(logn)级别的，所以我们一次区间访问用递归实现的复杂度同样是O（logn）；

实现代码：

void change(ll k,ll l,ll r,ll id,ll v) {//id是原序列的位置，v为需要更新的值
        if(l>id|| r<id) return ;
        if(l==r&& l==id) {
            m[k]=v//访问到叶节点直接修改
            return ;
        }
        ll mid=l+r>>1;
        change(k<<1, l, mid, id, v);
        change(k<<1|1, mid+1, r, id, v);
        m[k]=min(m[k<<1],m[k<<1|1]);//更新
    }

复杂度

我们将以上的三步复杂度整合，因为操作的次数为m次，所以线段树的总复杂度为O（mlogn）

延迟标记

我们会发现，当我们要修改一个区间的时候，如果某个节点被修改区间[L,R]完全覆盖那么以该节点为根的整棵子树的所有节点信息都会发生，如果逐一更新，那么复杂度就会变成O(n),显然无法接受。

我们再换个角度思考，如果我们现在修改了某个区间，点p所代表的区间[pl,pr]被区间[l,r]完全覆盖，逐一更新子树p中的所有节点

可是当后面查询指令的时候全完全没有用到这个子区间[L，R]，那么更新整棵子树都是徒劳的。

所以我们可以在回溯之前给p打上一个标记，意思为“该节点信息已被修改完但其子节点仍未更新”，这样的话如果后续的指令，需要p向下递归，我们再判断p是否有标记，如果有的话，就通过这个标记更新p的两个子节点，同时清除p的标记，给两个孩子打标记。

这样一来，每条修改或者查询区间的时间复杂度都降到了O（logN），延迟标记（懒惰标记）使得线段树从上到下传递信息，这对于今后解决问题也提供了一个重要思路。

注：前文提到的标记永久化在二维线段树与可持久化线段树有所应用，超出本篇概念的范围，之后会更新）

那么请看代码如何实现这一操作！

（以区间和为例）

//r(p)p的右孩子 
//l(p)左孩子 
void spread(int p)
{
    if(add(p))//如果有标记
    {
        sum(p<<1)+=add(p)*(r(p<<1)-l(p<<1)+1);
        sum(p<<1|1)+=add(p)*(r(p<<1|1)-l(p<<1|1)+1); //更新信息 
        add(p<<1)+=add(p);
        add(p<<1|1)+=add(p);//左右孩子打标记
        add(p)=0; //清除标记 
     } 
 } 

注意在修改区间的时候记得要给节点打上标记就好啦！

后续

学完以上内容，我们就可以做一些线段树的基础模板题。

比如说LOJ的130树状数组（事实上也可以通过线段树来实现）

POJ的3468，洛谷线段树的模板题，

有了最基础的框架，之后就是要学会运用啦

我将在后面的随笔中继续更新

参考：信息学奥赛一本通，OI wiki，算法竞赛进阶指南

如有错误请指正！

~未完待续。。。