记对线段树自己的理解

详细讲解了线段树。

线段树

前言

看了OI Wiki的线段树，最近几天琢磨明白了，分享一下我的理解。

线段树能做什么

线段树是一个能快速求区间和、区间最大值、区间最小值的数据结构。
它也可以单点修改、区间修改。
而上述操作的复杂度都是$\mathcal{O}(\log N)$，这无疑是迅速的。

它是如何实现的

建树

一开始我们有一个区间$[1,n]$，代表一个$n$长度的数组的所有值。
然后我们把他劈成两半，$[1,\lfloor\frac{1+n}{2}\rfloor]$和$[\lfloor\frac{1+n}{2}\rfloor+1,n]$，把这两个区间抽象为$[1,n]$的子节点。然后重复这个过程，把区间$[a,b]$劈成$[a,\lfloor\frac{a+b}{2}\rfloor]$和$[\lfloor\frac{a+b}{2}\rfloor+1,b]$。
这样整个数组就变成了一颗二叉树。

我们可以通过递归来完成线段树的建树，以区间求和为例，代码如下。

//原始数据，N为长度
int raw[N+1];
//线段树，通常要开四倍大小以应对最差情况，证明在https://www.luogu.com.cn/article/j8gzpv2p
int seg[4*N+1];
//值得注意的是，两个数组都是1索引
void build(int left,int right,int index){
    //区间只有一个元素的情况
    if(left==right){
        //把这个区间的和设置为这个元素的值
        seg[index]=a[left];
        return;
    }
    //(left+right)/2等于left+(right-left)/2，但后者在较大数据时不会溢出
    int mid=left+(right-left)/2;
    //index的叶子节点是2*index和2*index+1是一种二叉树存储技巧。
    //这样存储可以快速求一个下标对应的节点的左叶子节点和右叶子节点的下标
    //也可以快速求一个下表对应节点的父节点的下标
    build(left,mid,2*index);
    build(mid+1,right,2*index+1);
    seg[index]=seg[2*index]+seg[2*index+1];
}
int main(){
    //省略把数据读取到raw数组
    build(1o
}

容易发现建图的复杂度为$\mathcal{O}(n)$

区间查询

我们现在已经能完成这些节点上区间的查询了。
不难发现，我们只需要把一些线段树上区间求并集，就可以得到任意区间。
我们只要找离根节点的最短路的距离最低的、且是查询区间的子集的节点，就是那几个构成查询区间的线段树上区间。
这个部分比较简单，我就直接给代码了，还是以求和为例：

int raw[N+1];
int seg[4*N];
int get(int left,int right,int query_left,int query_right,int index){
    //是否是查询区间的子集
    if(left<=query_left&&right<=query_right){
        return seg[index];
    }
    int mid=left+(right-left)/2;
    int ret=0;
    //左叶子与查询区间有交集。query_right改成mid是缩小查询区间（分治思想）。
    if(query_left<=mid) ret+=get(left,mid,query_left,mid,2*index);
    //右叶子与查询区间有交集。query_left改成mid+1同理
    if(query_right>=mid+1) ret+=get(mid+1,right,mid+1,query_right,2*index+1);
    return ret;
}
int main(){
    //省略把数据读取到raw数组
    build(1,n,1);//n为数组长度
    get(1,n,a,b,1);//查询区间为[a,b]
}

需要注意一下query_left和query_right在分治的过程中的变动，这是一个很重要的细节。
区间查询的复杂度为$\mathcal{O}(\log N)$

区间修改与懒标记

我已信奉鸽子教，，，
所以我先不写

致谢

十分感谢OI Wiki，这个项目使我学到了很多知识。