线段树入门

LITFLYR · 2024-08-22 20:45:19 · 算法·理论

概念

更国际化的阅读方式
线段树是算法竞赛中常用的用来维护 区间信息 的数据结构。
线段树可以在 O(log N) 的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。
出自：OI Wiki
注：后面会讲复杂度的证明。

举例：现在有 n 个数，我需要对其进行如下操作：

1. 修改其中一个数。
2. 对其中连续的若干个数求和（求最大，最小等）。
3. 对其中连续的若干个数进行修改。

在使用数组存储时，对于操作1我们可以直接进行 O(1) 修改。而执行操作2或者操作3时，我们需要把整个数组扫一遍进行修改，这样的时间复杂度是 O(n) 的，而对于 k 次操作，复杂度可以达到 O(kn)，这样一旦数据范围过大，就很容易超时。所以这个时候，这种叫做线段树的数据结构就可以帮助我们达到 O(k log n) 的复杂度，在运行程序时速度就会大大加快。

首先，在学习线段树之前，我们需要对他的结构有所了解：

如图所示，线段树是一颗二叉树（每个节点最多有两个儿子），一颗线段树存储的是一段区间，如图所示他的根节点（图上节点1）表示整个区间，他的左儿子（图上节点2）和右儿子（图上节点3）将整个区间分成两段进行存储，直到不能再分为止。
观察图上，我们可以发现规律：
对于任意一个区间 [l,r]，有 mid=\lfloor \frac{l+r}{2} \rfloor，则该节点的左儿子表示区间 [l,mid]，右儿子表示区间 [mid+1,r]。
再观察节点编号，可以发现不是按照 1-n 连续存储，这是因为我们在记录线段树时通常使用一维数组，我们需要准确定位每个节点的左儿子和右儿子，因此他的存储具有一定规律性：
对于一个节点标号为 x 的点，他左儿子的标号为 2x，右儿子的标号为 2x+1。

代码实现

• 代码实现：建树

将区间输入之后，执行 build(1, 1, n)函数。其中第一个 1 表示当前节点标号，因为我们要从根节点开始操作故最开始节点标号为 1，随后的 1,n 表示区间的 l,r，因为是根节点所以记录整个区间。
在建树过程中，我们一定会走到叶子节点（没有儿子的节点），这个时候我们无法再继续向下建树，那我们该怎么返回呢？
其实只要在函数最开始做一个判断该节点(l==r)就好。
如果该节点不是叶子节点，我们需要继续建树，这时就需要用到递归的思想，将一个大区间分为两个小区间再处理。

#define ls(f) (f*2)//将代码中出现的 ls(f) 替换为 f*2
#define rs(f) (f*2+1)
void push_up(int f){//因为每次改变一个区间的时候，他的所有祖先都会被影响，所以需要向上更新。 
    //视情况而定，如果求和就更新 tre[f]=tre[ls(f)]+tre[rs(f)] 
    //也有可能是求最大值，最小值之类 
} 
void build(int f,int l,int r){
    if(l==r){
        tre[f]=a[l];//记录节点的值
        return ;
    }
    int mid=(l+r)>>1;//或写为 int mid=(l+r)/2; 效果相同
    build(ls(f),l,mid);//在这个区间没办法赋值，那我们就递归到可以赋值。         
    build(rs(f),mid+1,r);
    push_up(f); 
} 
int main(){
    cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i];
    build(1,1,n);
}

• 代码实现：区间查询（单点查询）

其实单点查询就是查询一个长度为 1 的区间，所以放在一起讲。
定义查询函数 query(1,1,n,x,y) ,分别表示当前节点，当前区间的边界，想要查询的区间。

如图，如果我要查询区间 [4,6]，可以发现他在树中是以 [4,5], [6,6] 的方式记录，所以在查询过程中我们需要把多段合在一起处理（相加，取最大、最小等）。在我们查询过程中，因为 [4,5] 已经包含在我们想要查询的区间里，就没有必要再递归 [4,4], [5,5] 了，所以这个函数的返回条件是 (x<=l&&r<=y)。其余思想与建树过程基本一致。

#define ls(f) (f*2)//将代码中出现的 ls(f) 替换为 f*2
#define rs(f) (f*2+1)
void push_up(int f){//因为每次改变一个区间的时候，他的所有祖先都会被影响，所以需要向上更新。 
    tre[f]=tre[ls(f)]+tre[rs(f)];//这里拿求和举例。 
} 
int query(int f,int l,int r,int x,int y){
    if(x<=l&&r<=y){
        return tre[f];
    }
    int mid=(l+r)>>1,ans=0;
    if(x<=mid) ans+=query(ls(f),l,mid,x,y);//如果要查询的区间没有覆盖当前区间的左儿子就没必要查询了
    if(mid<y) ans+=query(rs(f),mid+1,r,x,y);
    return ans; 
} 
int main(){
    cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i];
    build();
    cin >> x >> y;
    cout << query(1,1,n,x,y); 
}

复杂度证明：