『进阶』浅谈线段树

tyh0929 · 2025-01-24 16:23:36 · 算法·理论

一般线段树

初识线段树

一、问题产生

我们以本题为例，P3372 【模板】线段树 1。

二、问题分析

概括来说，本题题有两种操作：

• 1 l r x：将每个 a_i 增加 x，且 l \le i \le r。
• 2 l r：求出 [a_l,a_r] 之间的和。

本题的操作 1 为区间修改，操作 2 为区间求和。

三、寻找算法

1. 暴力（万物皆可暴力）

算法说明：

使用数组直接存储。操作 1 使用循环一次给每一个数加上 x；操作 2 也使用循环依次求和。

好处：

• 写法简便。
• 思路清晰。

坏处：

• 时间复杂度过高，为 O(nm)。

再看数据范围：1 \le n,m \le 10^5，TLE 无疑了。

2. 前缀和

算法说明：

使用前缀和数组存储。操作 1 需要将前缀和数组重新作处理；操作 2 可以直接算出。

好处：

• 前缀和对于区间求和可以 O(1) 求出，非常快速。

坏处：

• 前缀和只针对于静态区间，每次操作 1 都需要 O(n) 的时间，总时间复杂度仍为 O(nm)，依然无法通过本题。

所以只能处理静态数组的区间问题的算法都无法通过本题（如 ST 表）。

3. 差分

使用差分数组存储。操作 1 可以直接修改左右端点；操作 2 需要重新还原。

好处：

• 差分对于区间修改可以 O(1) 求出，不需要循环修改。

坏处：

• 差分求和需要重新还原，所以每次操作 2 都需要 O(n) 的时间算出，总时间复杂度仍为 O(nm)。

依然无法通过本题。

4. 树状数组

本算法也可过，因主讲线段树，现暂时省略。

5. 线段树（本场主角）

既然本题是动态区间查询问题，我们要让修改和查询时间复杂度都要降低。很多人都想到了树形结构和分治，我们将它们融合在一起，就成了线段树。

四、算法讲解

(1) 创建线段树

线段树既然是二叉树，就是二叉树的建树方法。

唯一不同的一点，就是这个结点的数据来源于其孩子节点的数据，有多添加一行计算代码。（可用函数封装）

代码如下：

struct asd{
    long long sum,tag;//sum:线段树数据（此为和）；tag:懒标记（见后文区间修改）
};
vector<asd>t;//创建线段树数组
int n,m;
asd merge(asd a,asd b){//封装结点计算函数
    asd ret{a.sum+b.sum,0};
    return ret;
}
void build(const vector<int> &a,int k,int cl,int cr){//创建线段树。k:结点编号；cl:指定查找区间左端点；cr:指定查找区间右端点
    if(cl==cr){//如果此结点为叶结点
        t[k].sum=a[cl];//赋值
        return;
    }
    int lc=k<<1,rc=lc+1;//计算左孩子和右孩子的编号
    int mid=(cl+cr)>>1;//计算中点
    build(a,lc,cl,mid);//向左孩子递归
    build(a,rc,mid+1,cr);//向右孩子递归
    t[k]=merge(t[lc],t[rc]);//计算当前结点
}
void init(const vector<int> &a){//初始化
    n=a.size();
    t.resize(n<<2);//记得开四倍空间
    build(a,1,1,n);//创建线段树
}

(2) 区间查询

我们画个图来理解：

本图为 n=5 的线段树，我们先进行区间查询：

我们要求出 [1,4] 内所有元素的和。

步骤如下：

第一步：[1,4] 在结点 [1,5] 左孩子和右孩子均有跨度，所以继续递归进入两个子节点。

第二步：[1,4] 包含结点 [1,3]，进行回溯；区间 [4,4] 在结点 [4,5] 的左孩子中，向左孩子进行递归。

第三步：[1,4] 结点包含 [4,4]，进行回溯。

从中，我们知道要查找指定区间的和或最小值等数据，需要递归查找区间所包含且线段树拥有的子区间。（如图中的 [1,3] 和 [4,4]）

代码如下：

long long qry(int k,int l,int r,int cl,int cr){//k:结点编号；l:此结点区间左端点；r:此结点区间右端点；cl:指定查找区间左端点；cr:指定查找区间右端点
    if(cl>r||cr<l){//如果此结点区间在指定查找区间之外
        return 0;//退出
    }
    if(cl>=l&&cr<=r){//如果指定查找区间完全包含此结点区间
        return t[k].sum;//返回子区间的数据
    }
    int lc=k<<1,rc=lc+1;//计算左孩子和右孩子的编号
    int mid=(cl+cr)>>1;//计算中点
    push_down(k,cl,cr);//懒标记向下传递（见后文区间修改）
    return qry(lc,l,r,cl,mid)+qry(rc,l,r,mid+1,cr);//回溯
}

(3) 区间修改

区间修改是最难想的一点，因为每次修改都要把区间的子区间都全部修改，时间复杂度仍然爆炸巨大，那怎么解决这个问题？

既然每次修改都要把区间的子区间都全部修改，那不如留个标记，等到要使用时再传到子区间并修改数据。

代码如下：

void push_down(int k,int cl,int cr){//下传懒标记
    int lc=k<<1,rc=lc+1;//计算左孩子和右孩子的编号
    int mid=(cl+cr)>>1;//计算中点
    t[lc].tag+=t[k].tag;//下传懒标记
    t[rc].tag+=t[k].tag;//下传懒标记
    t[lc].sum+=(mid-cl+1)*t[k].tag;//更新数据
    t[rc].sum+=(cr-mid)*t[k].tag;//更新数据
    t[k].tag=0;//删除原来的标记
}
void modify(int k,int l,int r,int cl,int cr,long long x){//区间修改
    if(cl>r||cr<l){//如果此结点区间在指定查找区间之外
        return;//退出
    }
    if(l<=cl&&r>=cr){//如果指定查找区间完全包含此结点区间
        t[k].tag+=x;//添加懒标记
        t[k].sum+=x*(cr-cl+1);//更新数据
        return;//退出
    }
    int lc=k<<1,rc=lc+1;//计算左孩子和右孩子的编号
    int mid=(cl+cr)>>1;//计算中点
    push_down(k,cl,cr);//下传懒标记
    modify(lc,l,r,cl,mid,x);//向左区间进行递归
    modify(rc,l,r,mid+1,cr,x);//向右区间进行递归
    t[k]=merge(t[lc],t[rc]);//计算更新后结点数据
}

完整代码如下：

# include<bits/stdc++.h>
using namespace std;
struct asd{
    long long sum,tag;
};
vector<asd>t;
int n,m;
asd merge(asd a,asd b){
    asd ret{a.sum+b.sum,0};
    return ret;
}
void push_down(int k,int cl,int cr){
    int lc=k<<1,rc=lc+1;
    int mid=(cl+cr)>>1;
    t[lc].tag+=t[k].tag;
    t[rc].tag+=t[k].tag;
    t[lc].sum+=(mid-cl+1)*t[k].tag;
    t[rc].sum+=(cr-mid)*t[k].tag;
    t[k].tag=0;
}
void build(const vector<int> &a,int k,int cl,int cr){
    if(cl==cr){
        t[k].sum=a[cl];
        return;
    }
    int lc=k<<1,rc=lc+1;
    int mid=(cl+cr)>>1;
    build(a,lc,cl,mid);
    build(a,rc,mid+1,cr);
    t[k]=merge(t[lc],t[rc]);
}
void init(const vector<int> &a){
    n=a.size();
    t.resize(n<<2);
    build(a,1,1,n);
}
long long qry(int k,int l,int r,int cl,int cr){
    if(cl>r||cr<l){
        return 0;
    }
    if(cl>=l&&cr<=r){
        return t[k].sum;
    }
    int lc=k<<1,rc=lc+1;
    int mid=(cl+cr)>>1;
    push_down(k,cl,cr);
    return qry(lc,l,r,cl,mid)+qry(rc,l,r,mid+1,cr);
}
void modify(int k,int l,int r,int cl,int cr,long long x){
    if(cl>r||cr<l){
        return;
    }
    if(l<=cl&&r>=cr){
        t[k].tag+=x;
        t[k].sum+=x*(cr-cl+1);
        return;
    }
    int lc=k<<1,rc=lc+1;
    int mid=(cl+cr)>>1;
    push_down(k,cl,cr);
    modify(lc,l,r,cl,mid,x);
    modify(rc,l,r,mid+1,cr,x);
    t[k]=merge(t[lc],t[rc]);
}

五、算法分析

好处：

• 快速，时间复杂度低，每次查询和修改均为 O(\log n)。
• 模板灵活，只需修改少部分代码，即可改变其作用。（最大值、最小值、加和、异或和、积等）
• 支持在线处理。

坏处

• 空间消耗大，要额外开 4 倍的大小。
• 代码复杂，检查难度高。

六、算法答疑

1. 为什么要开 4n 的大小？