线段树

libohan0905 · 2022-09-23 19:24:06 · 个人记录

题单

可能太久写的会比较难看QWQ

线段树

队列进出图上的方向

线段树区间修改求出总量

可持久化留下的迹象

我们伏身欣赏

——《膜你抄》

线段树可以处理很多符合结合律的操作（比如区间加，区间乘之类的），使其时间复杂度从 n^2 降到 n\log n，并支持区间修改和区间查询，甚至在以后某些算法还可以用线段树来优化

（其实能分治解决的都可以用 ~~只不过我们只能见过加加乘乘xor的~~）

比如区间加的实现：

P3372 【模板】线段树 1

题目描述

已知一个数列，你需要进行下面两种操作：

将某区间每一个数加上 k
求出某区间每一个数的和

1\leq n,m\leq 10^5
保证任意时刻数列中所有元素的绝对值之和 \leq 10^{18}

~~显然 n^2 暴力不行~~

但是，~~神奇的~~线段树可以 n\log n 完成本题！

存储

struct Tree {
    int l,r,len,lazy;
    long long data;
} T[MAXN];

l,r是左右节点编号，len是子树大小（就是这个点管几个数），lazy是懒标记（下面会讲），data是维护的值（就是这个点管的数加OR乘出来的结果）

建树

void Build(int k,int L,int R){
    T[k].l=L,T[k].r=R;
    T[k].lazy=0,T[k].len=R-L+1;
    if(L==R){
        T[k].data=a[L];
        return;
    }
    int mid=(L+R)>>1;
    Build(k<<1,L,mid);
    Build(k<<1|1,mid+1,R);
    T[k].data=T[k<<1].data+T[k<<1|1].data;
}

>>1即除以2，只是位运算会更快，<<1是乘2
|1不是+1，它对于奇数不改变，但偶数+1，所以在这里乘2后（一定是偶数）可以看成是+1
所以k*2是k的左儿子，k*2+1是k的右儿子

递归初始化，分治是线段树的核心

懒标记

就是它:lazy

可以说懒是线段树的精髓

它的核心思想是：

（区间加啦）
节点k：记懒标记上
（又区间加啦）
节点k：记懒标记上
（某天，区间查询）
节点k：快快快，懒标记别睡了，快起来把N年懒得加的值下传！
（一阵下传和计算后）
节点k：呼，更新我自己，清空懒标记，再返回答案，其实计算也不累嘛，懒标记都清空了，我也是全新的我了，我不能再懒下去了！
（区间加啦）
节点k：记懒标记上。。。

~~像极了赶暑假作业后的我~~

首先我们可以从上面我~~瞎写的~~例子中可以明白，如果我们要区间修改的话，我们不妨在区间进行修改时为该区间打上一个标记，就不必再修改他的儿子所维护区间，等到要使用该节点的儿子节点维护的值时，再将懒标记下传即可，可以节省很多时间 ~~而且这也不是你最后一天才写暑假作业的理由~~

那怎么懒标记下传呢？

懒标记下传pushdown

void pushdown(int k) {
    if(!T[k].lazy) return;
    T[k<<1].data=(T[k<<1].data+T[k<<1].len*T[k].lazy)%P;
    T[k<<1|1].data=(T[k<<1|1].data+T[k<<1|1].len*T[k].lazy)%P;
    T[k<<1].lazy=(T[k<<1].lazy+T[k].lazy)%P;
    T[k<<1|1].lazy=(T[k<<1|1].lazy+T[k].lazy)%P;
    T[k].lazy=0;
}

一次下传只传一个节点的左右儿子

（那它的左右儿子怎么办？等到要用我再算，对，它就这么懒）

区间修改

void SegmentTree_Add(int k,int L,int R,int val) {
    if(L<=T[k].l&&T[k].r<=R) {
        T[k].data+=T[k].len*val;
        T[k].lazy+=val;
        return;
    }
    pushdown(k);
    int mid=(T[k].l+T[k].r)>>1;
    if(L<=mid) SegmentTree_Add(k<<1,L,R,val);
    if(R>mid)  SegmentTree_Add(k<<1|1,L,R,val);
    T[k].data=T[k<<1].data+T[k<<1|1].data;
}

如果在范围里就先加节点上，然后儿子先不下传，记懒标记账上

如果不完全在范围里，一定还会往下访问，顺便把懒标记下传

如果压根不在这范围里？其实在我这个函数里不会出现，注意看我这里写法比较特殊，是在递归前就判断了下一次可不可行

区间查询

long long SegmentTree_Query(int k,int L,int R) {    
    if(L<=T[k].l&&T[k].r<=R)
        return T[k].data;
    pushdown(k);
    long long ans=0;
    int mid=(T[k].l+T[k].r)>>1;
    if(L<=mid) ans+=SegmentTree_Query(k<<1,L,R);
    if(R>mid)  ans+=SegmentTree_Query(k<<1|1,L,R);
    return ans;
}

核心思想和区间查询差不多，如果不懂的话再回去看看

完整代码

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2000005;
const long long P=2e18;
struct Tree {
    int l,r,len,lazy;
    long long data;
} T[MAXN];
int n,m,a[MAXN];
void Build(int k,int L,int R){
    T[k].l=L,T[k].r=R;
    T[k].lazy=0,T[k].len=R-L+1;
    if(L==R){
        T[k].data=a[L];
        return;
    }
    int mid=(L+R)>>1;
    Build(k<<1,L,mid);
    Build(k<<1|1,mid+1,R);
    T[k].data=(T[k<<1].data+T[k<<1|1].data)%P;
}
void pushdown(int k) {
    if(!T[k].lazy) return;
    T[k<<1].data=(T[k<<1].data+T[k<<1].len*T[k].lazy)%P;
    T[k<<1|1].data=(T[k<<1|1].data+T[k<<1|1].len*T[k].lazy)%P;
    T[k<<1].lazy=(T[k<<1].lazy+T[k].lazy)%P;
    T[k<<1|1].lazy=(T[k<<1|1].lazy+T[k].lazy)%P;
    T[k].lazy=0;
}
void SegmentTree_Add(int k,int L,int R,int val) {
    if(L<=T[k].l&&T[k].r<=R) {
        T[k].data+=T[k].len*val;
        T[k].lazy+=val;
        return;
    }
    pushdown(k);
    int mid=(T[k].l+T[k].r)>>1;
    if(L<=mid) SegmentTree_Add(k<<1,L,R,val);
    if(R>mid)  SegmentTree_Add(k<<1|1,L,R,val);
    T[k].data=(T[k<<1].data+T[k<<1|1].data+P)%P;
}
long long SegmentTree_Query(int k,int L,int R) {    
    if(L<=T[k].l&&T[k].r<=R)
        return T[k].data;
    pushdown(k);
    long long ans=0;
    int mid=(T[k].l+T[k].r)>>1;
    if(L<=mid) ans=(ans+SegmentTree_Query(k<<1,L,R))%P;
    if(R>mid)  ans=(ans+SegmentTree_Query(k<<1|1,L,R))%P;
    return ans;
}
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++) scanf("%d",&a[i]);
    Build(1,1,n);
    while(m--) {
        int op,x,y,z;
        scanf("%d",&op);
        if(op==1) {
            scanf("%d%d%d",&x,&y,&z);
            SegmentTree_Add(1,x,y,z);
        } else if(op==2) {
            scanf("%d%d",&x,&y);
            printf("%lld\n",SegmentTree_Query(1,x,y));
        }
    }
    return 0;
}

P3373 【模板】线段树 2

题目描述

已知一个数列，你需要进行下面三种操作：

将某区间每一个数加上 k
将某区间每一个数乘上 k
求出某区间每一个数的和

1\leq n,m\leq 10^5
输出区间 [x,y] 内每个数的和对 p 取模所得的结果

相当于多了一个乘法，那么我们多建立一个 mullazy 标记记录乘的数即可

代码还有很多细节，比如 mullazy 初始化为 1，区间乘法时 addlazy 也要乘，在 pushdown 时处理懒标记要先乘后加（为什么先乘后加不是先加后乘？因为在区间乘时我们已经乘过了），所以就算是模板题，还是很有必要亲自从头敲一遍的

下面就给出 pushdown 的代码：

inline void pushdown(long long k) {
    if(T[k].mullazy!=1) {
        T[k<<1].data=(T[k<<1].data*T[k].mullazy)%P;
        T[k<<1|1].data=(T[k<<1|1].data*T[k].mullazy)%P;
        T[k<<1].mullazy=(T[k<<1].mullazy*T[k].mullazy)%P;
        T[k<<1|1].mullazy=(T[k<<1|1].mullazy*T[k].mullazy)%P;
        T[k<<1].addlazy=(T[k<<1].addlazy*T[k].mullazy)%P;
        T[k<<1|1].addlazy=(T[k<<1|1].addlazy*T[k].mullazy)%P;
        T[k].mullazy=1;
    }
    if(!T[k].addlazy) return;
    T[k<<1].data=(T[k<<1].data+T[k<<1].len*T[k].addlazy)%P;
    T[k<<1|1].data=(T[k<<1|1].data+T[k<<1|1].len*T[k].addlazy)%P;
    T[k<<1].addlazy=(T[k].addlazy+T[k<<1].addlazy)%P;
    T[k<<1|1].addlazy=(T[k].addlazy+T[k<<1|1].addlazy)%P;
    T[k].addlazy=0;
}

~~别看那么长，都是复制的~~

如果你写出来了，奖励你一道双倍经验

习题

P2574 XOR的艺术
CF877E Danil and a Part-time Job 上一题加强版，可能会树剖可以更快
P8818 [CSP-S 2022] 策略游戏
CF438D The Child and Sequence

P4145 上帝造题的七分钟 2 / 花神游历各国

题目描述

一个正整数数列区间开方（下取整），区间求和

1\leq n,m\leq 10^5$，$1\leq l,r\leq n$，数列中的数大于 $0$，且不超过 $10^{12}

数据中有可能 l>r，所以遇到这种情况请交换 l 和 r

貌似是线段树，但开方无法得知具体数字，比如常规线段树的求区间和的这一段：

    if(L<=T[k].l&&T[k].r<=R) {
        T[k].data+=T[k].len*val;
        T[k].lazy+=val;
        return;
    }

我们发现我们不会改，因为它每次减少的跟具体的值有关

那我们换个思路，我们可以暴力开方每个顶点，再一层层往上推

但这样的话修改可以到 n^2，还不行

注意到 a[i]\leq 10^{12}，每个数至多六次开平方便可得到 1，给 1 开方无意义

如果是 1 的话跳过，那么在每个节点设一个is1来记录是否以它为根的全部叶节点是否都为1

用lazy来记录是否被修改，只有lazy==0才直接返回此节点的值

如果看到这里你已经急不可耐的交了，那么你会发现你很有可能还是暴力分

为什么呢？因为 is1 只方便了你修改，查询时最终还是会退化成暴力

我们可以用类似于 push_down 的思想

如果你这次探查了整个子树（即L<=l&&r<=R）

更新这个节点并清空lazy

完整代码

#include<bits/stdc++.h>
using namespace std;
const int M = 100005;
struct tree {
    long long data;
    bool is1,lazy;
} t[M*4];
int n,m;
long long a[M];
void build(int p,int l,int r) {
    t[p].lazy=0;
    if(l==r) {
        t[p].data=a[l];
        if(a[l]==1) t[p].is1=1;
        else t[p].is1=0;
        return;
    }
    int m=(l+r)>>1;
    build(p<<1,l,m);
    build(p<<1|1,m+1,r);
    t[p].data=t[p<<1].data+t[p<<1|1].data;
    t[p].is1=(t[p<<1].is1&&t[p<<1|1].is1);
}
long long query(int p,int l,int r,int L,int R) {
    if(l>R||r<L) return 0;
    if(l==r) return t[p].data;
    long long ans=0;
    if(L<=l&&r<=R&&t[p].lazy==0) {
        return t[p].data;
    }
    int m=(l+r)>>1;
    ans+=query(p<<1,l,m,L,R);
    ans+=query(p<<1|1,m+1,r,L,R);
    if(L<=l&&r<=R) {
        t[p].data=ans;
        t[p].lazy=0;
    }
    return ans;
}
void solve(int p,int l,int r,int L,int R) {
    if(l>R||r<L) return;
    if(t[p].is1) return;
    if(l==r) {
        t[p].data=sqrt(t[p].data);
        if(t[p].data==1) t[p].is1=1;
        return;
    }
    int m=(l+r)>>1;
    solve(p<<1,l,m,L,R);
    solve(p<<1|1,m+1,r,L,R);
    t[p].is1=(t[p<<1].is1&&t[p<<1|1].is1);
    t[p].lazy=1;
}
int main() {
    scanf("%d",&n);
    for(int i=1; i<=n; i++) {
        scanf("%lld",&a[i]);
    }
    scanf("%d",&m);
    build(1,1,n);
    for(int i=1; i<=m; i++) {
        int op,x,y;
        scanf("%d",&op);
        scanf("%d%d",&x,&y);
        if(x>y) swap(x,y);
        if(op==0) {
            solve(1,1,n,x,y);
        } else {
            printf("%lld\n",query(1,1,n,x,y));
        }
    }
}

双倍经验：GSS4 - Can you answer these queries IV

习题

CF438D The Child and Sequence 我们会发现一个结论：每个数取模后如果它改变了，那么它必然缩小至少二分之一。
P7334 [JRKSJ R1] 吊打

P6327 区间加区间sin和

可持久化线段树

又称主席树，比线段树多一个可以查询/修改历史版本的功能

且时间复杂度和空间复杂度均为 n\log n 的毒瘤优秀算法

建议详细了解线段树再来看

线段树

题单

可能太久写的会比较难看QWQ

线段树

P3372 【模板】线段树 1

题目描述

存储

建树

懒标记

区间修改

区间查询

完整代码

P3373 【模板】线段树 2

题目描述

习题

P4145 上帝造题的七分钟 2 / 花神游历各国

题目描述

完整代码

习题

P6327 区间加区间sin和

可持久化线段树

详细解释