数据结构-线段树

4FGR2025-04-032025-04-07

线段树

数据结构系列一下子跳到线段树了，私密马赛，最近太急于蓝桥杯比赛了，落后的教程一定会补上QAQ!

参考: 线段树 - OI Wiki

线段树是一种二叉搜索树、平衡二叉树，对于区间的修改、维护和查询时间复杂度优化为log级别。对区间不断做平分区间，直到划分到只有一个或多个数据的区间，可表示区间的和或者最小最大值。在进行更新区间操作时，通过小区间更新大区间。

对于下面的内容，我们主要针对于区间加法的线段树(即其节点表示区间之和)。

局限性：

问题需满足区间加法：对于[L,R]的区间，它的答案可以由[L,M]和[M+1,R]的答案合并求出。
不满足区间的众数、区间最长连续问题、最长不下降问题等。

建树

当我们拥有数组并且用来区间求和之类的问题时，我们可以这样做：

以堆的方式实现存储(树形数组)，将元素放至树的最下面一层。

由于我们使用树形数组，为了存储下数组 , 数组的长度应当为的四倍，并且初始节点位置为1。同时，当前区间[s,t]只有一个元素时(即s==t)，意味着当前节点为叶子节点，就要让当前节点。对于其它的情况，我们求得当前区间的中间数来区分左子树和右子树，并使用递归创建左子树和右子树，最后将左孩子和右孩子节点的值之和赋值给当前节点。

显然，初始建树时使用build(1,n,1)

代码实现

const int N = 100000;
int a[N];
int tree[4*N];
void build(int s,int t,int p){
    if(s == t){
        tree[p] = a[s];
    }else{
        int m = s+((t-s)>>1); //使用位运算更快
        build(s,m,p*2); //建立左子树
        build(s,m,p*2+1); //建立右子树
        tree[p] = tree[p*2]+tree[p*2+1];
    }
}

区间修改

我们假设目标区间为[l,r],当前区间为[s,t], 对目标区间的所有元素均加上值

由于是对目标区间的修改，很可能我们不用遍历完叶子节点，在当前区间刚好覆盖目标区间，或者目标区间由多个节点组成时，由于所有区间都是加上一个相同的值，我们可以修改结果为

当 前 值 当 前 区 间 的 个 数

修改完节点后记住要更新之前节点。

出于效率的需要，我们会用到懒惰标记将此区间标记，表示这个区间的值已经更新，但它的子区间却没有更新，更新的信息就是标记里存的值。

区间修改步骤:

如果要修改的区间完全覆盖当前区间，直接更新这个区间，加上标记（表示区间内元素加k）
如果没有完全覆盖，且当前区间有标记，先下传标记到子区间，再清除当前区间的标记
如果修改区间和左儿子有交集，搜索左儿子(避免死递归)
如果修改区间和右儿子有交集，搜索右儿子
最后将当前区间的值更新, 即节点的值为子节点值之和

int lazy[4*N];
void update(int l,int r,int k,int s,int t,int p){
    if(l<=s && t<=r){
        tree[p] += (t-s+1)*k;
        lazy[p] += k;
    }else{
        int m = s+((t-s)>>1);
        //检查是否要下传lazy标记
        if(lazy[p]){  //注意是否p*2超过数组长度，可以用s!=t的条件限制
            tree[p*2] += (m-s+1)*lazy[p];
            tree[p*2+1] += (t-m)*lazy[p];
            lazy[p*2] += lazy[p];
            lazy[p*2+1] += lazy[p];
            lazy[p] = 0; //清空标记
        }
        if(l<=m) update(l,r,s,m,1,p*2); //左孩子区间与目标区间有交集
        if(r>m) update(l,r,m+1,t,p*2+1); //右孩子区间与目标区间右交集
        tree[p] = tree[p*2] + tree[p*2+1]; //更新当前节点
    }
}

区间查询

我们想要得到的区间和，和区间修改同理，在当前区间被覆盖时，就返回对应值，否则就搜索当前节点的左孩子和有孩子(注意到，只有对应区间与目标区间有交集时才搜索)，注意存在懒惰标记时需要下传。

步骤如下:

如果要查询的区间完全覆盖当前区间，直接返回当前节点的值
如果没有被完全包含当前区间，下传标记
如果查询区间和左儿子有交集，搜索左儿子
如果查询区间和右儿子有交集，搜索右儿子
最后合并相关数据

int getsum(int l,int r,int s,int t,int p){
    if(l<=s && r<=t){
        return tree[p];
    }else{
        int m = s + ((t-s) >> 1);
        //检查是否要下传lazy标记
        if(lazy[p]){  //注意是否p*2超过数组长度，可以用s!=t的条件限制
            tree[p*2] += (m-s+1)*lazy[p];
            tree[p*2+1] += (t-m)*lazy[p];
            lazy[p*2] += lazy[p];
            lazy[p*2+1] += lazy[p];
            lazy[p] = 0; //清空标记
        }
        int sum = 0;
        if(l<=m) sum=getsum(l,r,s,m,p*2);
        if(r>m) sum+=getsum(l,r,s,m+1,p*2+1);
        return sum;
    }
}

模板

// 线段树区间加法和区间求和
#include<bits/stdc++.h>

using namespace std;
using ll = long long;
const ll N = 1000000;
ll a[N];
ll tr[4*N];
vector<ll> lazy(4*N,0);

//对区间[s,t]建树，p为当前节点编号
void build(ll s,ll t,ll p){ //建树
    if(s == t){
        tr[p] = a[s];
        return;
    }
    else{
        ll m = s + ((t-s)>>1);
        build(s,m,p*2);
        build(m+1,t,p*2+1);
        tr[p] = tr[p*2] + tr[p*2+1];
    }
}

//更新区间[l,r]，[s,t]为当前节点区间，p为当前节点编号
void update(ll l, ll r, ll c, ll s,ll t,ll p){
    if(l <= s && t <= r){
        tr[p] += c*(t-s+1);
        lazy[p] += c;
        return;
    }else{
        ll m = s+((t-s)>>1);
        if(lazy[p]){
            tr[p*2] += lazy[p]*((m-s+1));
            tr[p*2+1] += lazy[p]*((t-m));
            lazy[p*2] += lazy[p];
            lazy[p*2+1] += lazy[p];
            lazy[p] = 0;
        }  
        if(l <= m) update(l,r,c,s,m,p*2);
        if(r > m) update(l,r,c,m+1,t,p*2+1);
        tr[p] = tr[p*2] + tr[p*2+1];
    }
}

//区间求和
ll getsum(ll l,ll r,ll s,ll t,ll p){
    if(l <= s && t <= r){
        return tr[p];
    }
    ll m = s + ((t-s)>>1);
    ll sum = 0;
    if(lazy[p]){
        tr[p*2] += lazy[p]*((m-s+1));
        tr[p*2+1] += lazy[p]*((t-m));
        lazy[p*2] += lazy[p];
        lazy[p*2+1] += lazy[p];
        lazy[p] = 0;
    }
    if(l <= m) sum = getsum(l,r,s,m,p*2);
    if(r > m) sum += getsum(l,r,m+1,t,p*2+1);
    return sum;
}



int main(){
    ll n,m;
    cin >>  n >> m;
    for(ll i = 1; i <= n; i++){
        cin >> a[i];
    }
    build(1,n,1);
    while(m--){
        ll op;
        cin >> op;
        //1表示区间加法，2表示区间求和
        if(op == 1){
            ll x,y,k;
            cin >> x >> y >> k;
            update(x,y,k,1,n,1);
        }else if(op == 2){
            ll x,y;
            cin >> x >> y;
            cout << getsum(x,y,1,n,1) << endl;
        }
    }
}

实例

P3870 [TJOI2009] 开关 - 洛谷

对于这道题，我们知道:

区间修改不需要参数k，我们需要做的仅仅是将状态逆转,因此除了修改区间、当前区间、当前位置外，就不再需要别的参数
当灯开为1，灯关为0时，区间查询(区间求和)的结果就是答案。由于初始时，灯全部是关闭的，那么执行build函数时,只需要让即可

同时，我们很容易发现对于区间而言，区间灯开着的个数和灯关着的个数相加为，于是乎，对于第一种操作”逆转灯泡”而言，我们只需要执行即可。同理可得下传懒惰标记时的处理方法。

另一种不需要数学的解法是，我们同时存储逆转后的值，记为, 在build时令其为1，在更新区间和下传标记时使用swap函数交换两种。

/*伪代码,[l,r]为修改区间,[s,t]为当前区间,p为当前位置*/
void modify(l,r,s,t,p){
	if(l<=s&&t<=r){
		tree[p] = (t-s+1)-tree[p];  //或者 swap(tree[p],constract[p]);
        /*这里lazy[p]该如何操作呢?*/
	} else{
		int m = s+((t-s)>>1);
        if(lazy[p]){
            tree[p*2] = (m-s+1) - tree[p*2];  //swap(tree[p*2],constract[p*2])
            tree[p*2+1] = (t-m) - tree[p*2+1]; //swap(tree[p*2+1],constract[p*2+1]);
            /*lazy的子节点该如何更新呢？*/
            lazy[p] = false;
        }
	}
}

实际上，这道题的最关键点在于对懒惰标记的处理。

我们很容易想到，由于灯泡只有两种状态，那么懒惰标记应该可以用和表示，表示该区间已逆转，当搜索当该区间时下传区间。当然，表示该区间未被逆转。

这是对的,但是在实际操作中我们也许会发现这样的错误：在更新区间的最后标记 $lazy[p]为true;在下传lazy[p]$ 时，令其孩子节点的 $lazy$ 值为或者说 $lazy[p]$ 。

实际上，当我们重复更新相同区间时, 之前已经为的会被再次被赋值为 , 但可能 $tree[p]$ 的值已经恢复原样了。同理，当我们下传懒惰标记时, 很可能其孩子节点已经为 , 从而造成了下传的混乱。我们很容易使用if条件解决，但为了方便起见，我们用0和1表示懒惰标记，并用异或操作^进行处理。

解决代码如下:

#include<bits/stdc++.h>

using namespace std;

//开数组
const int N = 1000000;
int constract[4*N];
int tree[4*N]; //线段树
vector<int> lazy(4*N,0); //懒标记

//线段树的建立
void build(int s, int t, int p){
    if(s == t){
        tree[p] = 0;  // 初始灯泡关闭
    }else{
        int m = s+((t-s)>> 1);
        build(s, m, p*2);
        build(m+1, t, p*2+1);
        tree[p] = tree[p*2] + tree[p*2+1];
    }
}

//区间修改,目标区间[l,r],[s,t]为当前区间，将目标区间的值逆转
void modify(int l,int r,int s, int t,int p){
    if(l<=s && t<=r){
        tree[p] = (t-s+1)-tree[p]; //逆转灯泡
        lazy[p]^=1;  //逆转状态
    }
    else{
        int m = s+((t-s)>>1);
        
        if(lazy[p]){ //将懒标记下传
            tree[2*p] = (m-s+1) - tree[p*2];
            tree[2*p+1] = (t-m) - tree[p*2+1];
            lazy[p*2] ^= lazy[p];
            lazy[p*2+1] ^= lazy[p];
            lazy[p] = 0; //将标记清空
        }
        
        if(l<=m) modify(l,r,s,m,p*2); //部分元素被包含在左孩子，搜索左子树
        if(r>m)modify(l,r,m+1,t,p*2+1); //部分元素被包含在右孩子，搜索右子树
        tree[p] = tree[p*2] + tree[p*2+1];  //修改后,记得更新节点
    }
}
//查询区间[l,r]的总和，即区间中亮着的灯泡数
int getsum(int l, int r,int s, int t,int p){
    int res = 0;
    if(l<=s && t<=r){
        res = tree[p];
    }else{
        int m = s+((t-s)>>1);

        if(lazy[p]){ //将懒标记下传
            tree[2*p] = (m-s+1) - tree[p*2];
            tree[2*p+1] = (t-m) - tree[p*2+1];
            lazy[p*2] ^= lazy[p];
            lazy[p*2+1] ^= lazy[p];
            lazy[p] = 0; //将标记清空
        }
        if(l<=m) res += getsum(l,r,s,m,p*2);
        if(r>m)res += getsum(l,r,m+1,t,p*2+1);
    }
    return res;
}

int main(){
    int n,m;
    cin >> n >> m;
    //建立线段树
    build(1,n,1);
    for(int c=0;c<m;c++){
        int op,a,b;
        cin >> op >> a >> b;
        if(op == 0){
            modify(a,b,1,n,1); //逆转灯泡状态
        }else if(op == 1){
            cout << getsum(a,b,1,n,1) << endl;  //输出结果
        }
    }
}