线段树&数链剖分

傻逼线段树，傻逼数剖

线段树

定义：

线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。

使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(logN)。而未优化的空间复杂度为2N，实际应用时一般还要开4N的数组以免越界，因此有时需要离散化让空间压缩。

有什么用？

线段树功能强大，支持区间求和，区间最大值，区间修改，单点修改等操作。
线段树的思想和分治思想很相像。
线段树的每一个节点都储存着一段区间[L…R]的信息，其中叶子节点L=R。它的大致思想是：将一段大区间平均地划分成2个小区间，每一个小区间都再平均分成2个更小区间……以此类推，直到每一个区间的L等于R（这样这个区间仅包含一个节点的信息，无法被划分）。通过对这些区间进行修改、查询，来实现对大区间的修改、查询。
这样一来，每一次修改、查询的时间复杂度都只为O(log₂n)。

建树：

void build(int l,int r,int i){//建树，为当前左边界，r为右边界，i为编号

     tree[i].l=l;//更新边界值

     tree[i].r=r;

     if(l==r){//如果是最底层的节点，sum就是本身

         tree[i].sum=input[l];

         return ;

    }

    int mid=(l+r)/2;

    build(l,mid,2*i);//左边部分建树

    build(mid+1,r,2*i+1);//右边部分建树

    tree[i].sum=(tree[2*i].sum+tree[2*i+1].sum)%mod;//递归返回时更新sum值

 }

区间修改：

void add(int i,int L,int R,int k){//区间修改  ;

     if(tree[i].l>=L&&tree[i].r<=R){//被完全包含

         tree[i].sum=tree[i].sum+(tree[i].r-tree[i].l+1)*k; //修改区间

         tree[i].lazy+=k;//更新延迟标记

         return ;

    }

    push_down(i);//没有完全包含的话就先下传懒标记

    int mid=(tree[i].l+tree[i].r)/2;

    if(L<=mid) add(2*i,L,R,k);//左边有重合走左边

    if(mid<R) add(2*i+1,L,R,k);//右边有重合走右边

//这里一定不能写mid<=R，不然会死循环

    tree[i].sum=tree[2*i].sum+tree[2*i+1].sum//更新sum值

 }

区间查询：

int ask(int i,int L,int R){//区间查询

     if(tree[i].l>=L&&tree[i].r<=R) return tree[i].sum;//完全包含，道理同区间修改

     push_down(i);//没有完全包含就下传延迟标记

     int ans=0;

     int mid=(tree[i].l+tree[i].r)/2;

     if(mid>=L) ans=(ans+ask(2*i,L,R));

     if(mid<R) ans=(ans+ask(2*i+1,L,R));//记录答案

     return ans;

 }

下传延迟标记（push_down操作）：

void push_down(int i){//延迟标记下移

     if(tree[i].lazy){

         tree[2*i].sum=(tree[2*i].sum+(tree[2*i].r-tree[2*i].l+1)* tree[i].lazy%mod)%mod;

         tree[2*i+1].sum=(tree[2*i+1].sum+(tree[2*i+1].r-tree[2*i+1].l+1)* tree[i].lazy%mod)%mod;

        tree[2*i].lazy+=tree[i].lazy;

        tree[2*i+1].lazy+=tree[i].lazy;

        tree[i].lazy=0;

     }

 }

延迟标记的作用：

有些时候修改了也不一定会去查询，于是就打上延迟标记，需要的时候再下传。

板题：https://www.luogu.com.cn/problem/P3372

Code:

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+5;

int n,m;

int type,x,y,k;

long long input[N];

struct node {

    int l;

    int r;

    long long sum;

    long long add;

} tree[N*4];

void spread(int i) {

    if(tree[i].add) {

        tree[2*i].sum+=tree[i].add*(tree[2*i].r-tree[2*i].l+1);

        tree[2*i+1].sum+=tree[i].add*(tree[2*i+1].r-tree[2*i+1].l+1);

        tree[2*i].add+=tree[i].add;

        tree[2*i+1].add+=tree[i].add;

        tree[i].add=0;

    }

}

void build(int i,int l,int r) {

    tree[i].l=l;

    tree[i].r=r;

    if(l==r) {

        tree[i].sum=input[l];

        return ;

    }

    int mid=(l+r)/2;

    build(2*i,l,mid);

    build(2*i+1,mid+1,r);

    tree[i].sum=tree[2*i].sum+tree[2*i+1].sum;

}

void change(int i,int l,int r,int k) {

    if(l<=tree[i].l&&r>=tree[i].r) {

        tree[i].sum+=k*(tree[i].r-tree[i].l+1);

        tree[i].add+=k;

        return ;

    }

    spread(i);

    int mid=(tree[i].l+tree[i].r)/2;

    if(l<=mid)change(2*i,l,r,k);

    if(r>mid)change(2*i+1,l,r,k);

    tree[i].sum=tree[2*i].sum+tree[2*i+1].sum;

}

long long check(int i,int l,int r) {

    if(l<=tree[i].l&&r>=tree[i].r) {

        return tree[i].sum;

    }

    spread(i);

    long long flag=0;

    int mid=(tree[i].l+tree[i].r)/2;

    if(l<=mid) flag+=check(2*i,l,r);

    if(r>mid) flag+=check(2*i+1,l,r);

    return flag;

}

int main() {

    cin>>n>>m;

    for(int i=1; i<=n; i++) {

        cin>>input[i];

    }

    build(1,1,n);

    for(int i=1; i<=m; i++) {

        cin>>type;

        if(type==1) {

            cin>>x>>y>>k;

            change(1,x,y,k);

        }

        if(type==2) {

            cin>>x>>y;

            cout<<check(1,x,y)<<endl;

        }

    }

    return 0;

}

好的接下来来到——

树剖

定义：我们以某种规则将一棵树剖分成若干条竖直方向上的链，每次维护时可以一次跳一条链、并借助一些强大的线性数据结构来维护（通常链的数量很少），这样就大大优化了时间复杂度，足以解决很多线性结构搬到树上的题目。

变量：

//son[N] 重儿子的编号，若没有重儿子则编号为-1

//size[N] 子树的大小

//f[N] 父亲节点的编号

//d[N] 结点的深度

//top[N] 所在链的链端

//id[N] 经过重链剖分后的新编号

//rk[N] 有rk[id[i]]=i

将树剖分成链的过程中，我们一共要进行两次dfs:

void dfs1(int x,int fa,int depth){//x:当前结点 fa:父结点 depth:当前结点深度

     f[x]=fa;//更新父结点

     d[x]=depth;//更新深度

     size[x]=1;//子树大小初始化：根节点本身

     for(int i=head[x];i;i=nex[i]){

         int y=ver[i];

         if(y==fa) continue ;

         dfs1(y,x,depth+1);

        if(size[y]>size[son[x]]) son[x]=y;//更新重儿子

        size[x]+=size[y];//更新子树大小

     }

     return ;

 } //dfs1更新f[N],d[N],size[N],son[N]

 void dfs2(int u,int t){//u为当前结点，t为链段

     top[u]=t;

     id[u]=++cnt;

     rk[cnt]=u;//新的编号

     if(!son[u]) return ;

     dfs2(son[u],t);//优先遍历重儿子，使一条链上编号连续

     for(int i=head[u];i;i=nex[i]){

         int y=ver[i];

        if(y==son[u]||y==f[u]) continue;

        dfs2(y,y);//再建一条链

     }

 }//dfs2更新top[N],id[N],rk[N]

至此我们剖分的过程就已经完成了，现在让我们看看在题目中树链剖分有什么用：

题目：https://www.luogu.com.cn/problem/P3384

题目要求我们进行如下操作：

操作 1：格式： 1 x y z 表示将树从 x 到 y 结点最短路径上所有节点的值都加上 z。（区间修改）

操作 2：格式： 2 x y 表示求树从 x 到 y 结点最短路径上所有节点的值之和。（区间查询）

操作 3：格式： 3 x z 表示将以 x 为根节点的子树内所有节点值都加上 z。（区间修改）

操作 4：格式： 4 x 表示求以 x 为根节点的子树内所有节点值之和。（区间查询）

操作一：

void func1(int x,int y,int k){//将树从 x到 y结点最短路径上所有节点的值都加上k

     if(d[x]<d[y]) swap(x,y);

     while(top[x]!=top[y]){//循环，直到这两个点处于同一条链

         if(d[top[x]]<d[top[y]]) swap(x,y);//规范

         add(1,id[top[x]],id[x],k);

         x=f[top[x]];

     }

     if(d[x]>d[y]) swap(x,y);//深度较浅的一定是序号较小的

     add(1,id[x],id[y],k);

 }

其实原理就和倍增求LCA差不多。

操作二：

void func2(int x,int y){

     int ans=0;

     while(top[x]!=top[y]){

         if(d[top[x]]<d[top[y]]) swap(x,y);

         ans=(ans+ask(1,id[top[x]],id[x]))%mod;

         x=f[top[x]];

     }

     if(d[x]>d[y]) swap(x,y);//道理同上

     ans=(ans+ask(1,id[x],id[y]));

     cout<<ans%mod<<endl;

 }

原理和func1差不多啦~

操作三&&操作四：

这里的处理比较巧妙。

在树剖中，一条链的编号是连续的，因此一棵子树的编号也是连续的。

所以直接用线段树的区间修改和区间查询操作就行了。

Code:

#include<bits/stdc++.h>

#define int long long

using namespace std;

const int N=1e6+5;

int n,m,root,mod;

int idx=0;

 struct node{

     int l;

     int r;

     int sum;

     int lazy;

 }tree[4*N];

 int head[N],ver[2*N],nex[2*N],son[N],size[N],f[N],d[N],top[N],id[N],rk[N];

 int input[N];

 int cnt=0;

 void add_e(int x,int y){

     ver[++idx]=y;

     nex[idx]=head[x];

     head[x]=idx;

 }

 void build(int l,int r,int i){//常规建树

     tree[i].l=l;

     tree[i].r=r;

     if(l==r){

         tree[i].sum=input[rk[l]]%mod;

         return ;

    }

    int mid=(l+r)/2;

    build(l,mid,2*i);

    build(mid+1,r,2*i+1);

    tree[i].sum=(tree[2*i].sum+tree[2*i+1].sum)%mod;

 }

 void push_down(int i){//延迟标记下移

     if(tree[i].lazy){

         tree[2*i].sum=(tree[2*i].sum+(tree[2*i].r-tree[2*i].l+1)* tree[i].lazy%mod)%mod;

         tree[2*i+1].sum=(tree[2*i+1].sum+(tree[2*i+1].r-tree[2*i+1].l+1)* tree[i].lazy%mod)%mod;

        tree[2*i].lazy+=tree[i].lazy;

        tree[2*i+1].lazy+=tree[i].lazy;

        tree[i].lazy=0;

     }

 }

 int ask(int i,int L,int R){//区间查询

     if(tree[i].l>=L&&tree[i].r<=R) return tree[i].sum;

     push_down(i);

     int ans=0;

     int mid=(tree[i].l+tree[i].r)/2;

     if(mid>=L) ans=(ans+ask(2*i,L,R))%mod;

     if(mid<R) ans=(ans+ask(2*i+1,L,R))%mod;

     return ans%mod;

 }

 void add(int i,int L,int R,int k){//区间修改  ;

     if(tree[i].l>=L&&tree[i].r<=R){

         tree[i].sum=(tree[i].sum+(tree[i].r-tree[i].l+1)*k%mod)%mod;

         tree[i].lazy+=k;

         return ;

    }

    push_down(i);

    int mid=(tree[i].l+tree[i].r)/2;

    if(L<=mid) add(2*i,L,R,k);

    if(mid<R) add(2*i+1,L,R,k);

    tree[i].sum=(tree[2*i].sum+tree[2*i+1].sum)%mod;

 }

 void dfs1(int x,int fa,int depth){//x:当前结点 fa:父结点 depth:当前结点深度

     f[x]=fa;//更新父结点

     d[x]=depth;//更新深度

     size[x]=1;//子树大小初始化：根节点本身

     for(int i=head[x];i;i=nex[i]){

         int y=ver[i];

         if(y==fa) continue ;

         dfs1(y,x,depth+1);

        if(size[y]>size[son[x]]) son[x]=y;//更新重儿子

        size[x]+=size[y];//更新子树大小

     }

     return ;

 } 

 void dfs2(int u,int t){//u为当前结点，t为链段

     top[u]=t;

     id[u]=++cnt;

     rk[cnt]=u;//新的编号

     if(!son[u]) return ;

     dfs2(son[u],t);//优先遍历重儿子，使一条链上编号连续

     for(int i=head[u];i;i=nex[i]){

         int y=ver[i];

        if(y==son[u]||y==f[u]) continue;

        dfs2(y,y);//再建一条链

     }

 }

 void func1(int x,int y,int k){//将树从 x到 y结点最短路径上所有节点的值都加上k

     if(d[x]<d[y]) swap(x,y);

     while(top[x]!=top[y]){//循环，直到这两个点处于同一条链

         if(d[top[x]]<d[top[y]]) swap(x,y);//规范

         add(1,id[top[x]],id[x],k);

         x=f[top[x]];

     }

     if(d[x]>d[y]) swap(x,y);//深度较浅的一定是序号较小的

     add(1,id[x],id[y],k);

 }

 void func2(int x,int y){

     int ans=0;

     while(top[x]!=top[y]){

         if(d[top[x]]<d[top[y]]) swap(x,y);

         ans=(ans+ask(1,id[top[x]],id[x]))%mod;

         x=f[top[x]];

     }

     if(d[x]>d[y]) swap(x,y);//道理同上

     ans=(ans+ask(1,id[x],id[y]));

     cout<<ans%mod<<endl;

 }

signed main(){

    cin>>n>>m>>root>>mod;

    for(int i=1;i<=n;i++){

        cin>>input[i];//输入节点初始值

    }

    for(int i=1;i<=n-1;i++){

        int x,y;

        cin>>x>>y;

        add_e(x,y);

        add_e(y,x);//建图

    }

    dfs1(root,0,1);//第一次dfs求son,depth,f,size

    dfs2(root,root);//第二次dfs求id,rk,将树拆成链表

    build(1,n,1);//建树

    for(int i=1;i<=m;i++){

        int type;

        cin>>type;

        if(type==1){

            int x,y,z;

            cin>>x>>y>>z;

            func1(x,y,z);

        }

        if(type==2){

            int x,y;

            cin>>x>>y;

            func2(x,y);

        }

        if(type==3){

            int x,z;

            cin>>x>>z;

            add(1,id[x],id[x]+size[x]-1,z);

        }

        if(type==4){

            int x;

            cin>>x;

            cout<<ask(1,id[x],id[x]+size[x]-1)%mod<<endl;

        }

    }

    return 0;

}

完结撒花*★,°*:.☆(￣▽￣)/$:*.°★* 。

巴特西

线段树&数链剖分

最新文章

热门文章