LOADING

加载过慢请开启缓存 浏览器默认开启

线段树入门

入坑又爱又恨的线段树

线段树是将一段下标 1-n 的数组划分为一颗二叉搜索树,何为二叉搜索树呢,如下图所示

每一个可以继续延申的节点都有两个儿子,
且每一个节点下标k的两个儿子节点的下标分别是k+k和k+k+1,线段是利用这个特性,将1-n的一个区间不断分为两个又两个区间,

线段树的操作主要分为三个部分

建树(线段树初始化)

插入(对区间进行操作)

查找(获取区间的值)

每次的插入和查找的复杂度均为O(logn),总复杂度O(nlogn).

不难发现的是,我们可以用每一个节点表示两个儿子的和,从下网上递归得出每一个区间得和。

void build(int k, int l, int r) {
    if(l == r) {
        //num是输入的数组值
        f[k] = num[l];
        return; 
    }
    int m=(l+r)>>1;
    //递归左子树
    build(k+k, l, m);

    //递归右子树
    build(k+k+1, m + 1, r); 

    f[k]=f[k+k]+f[k+k+1]; 
    //递归更新
}

当我们给下标为4的位置+1时,可以发现他的往上的节点都会+1,改递归操作应从上往下进行,
开始发现4∈(1-4),则(1-4)+1,
然后发现4∈(3-4),则(3-4)+1,
最后4∈(4),则(4)+1。

void in(int k, int l, int r, int x, int v) {
    f[k]+=v;
    if(l==r) return;
    int m=(l+r)>>1;

    //递归子树
    if(x<=m) 
        //修改的区间完全在左区间
        in(k+k, l, m, x, val);
    else 
        //修改的区间完全在右区间
        in(k+k+1, m + 1, r, x, val); 
}

进行区间加值时

我们可以对这个操作进行优化,当进行区间加值时,如对3-4区间+1
开始发现(3-4)∈(1-4),则(1-4)+1,
然后发现(3)∈(1-2),4∈(3-4),则(1-2)+1,(3-4)+1,
最后3∈(3),4∈(4),则(3)+1,(4)+1。
在我们对区间进行范围性加法运算的时候,需要用个数组对节点下标进行标记,表示加法运算到该节点结束

要注意的是

我们使用标记是使得所有包含更改区间的节点都能更新值,且到完全覆盖修改区间的时候标记不下传
刚开始我想过,能不能不用 标记,直接包含的每段区间都 f[k]+=(y-x+1)*t; 就好了,结果是不行的,
如果不用标记,我修改了(1-4)的值+1,会在第一个节点停止,当我查询(2-3)的时候,会一直递归找到(2),(3)的值,发现并不能获取更新后的值,所以需要标记来记录更新。

void in(int k,int l,int r,int x,int y,ll t){
  //当前节点为k,lr为节点的区间范围,xy为所要修改的区间范围,t为要加的值
    if(l==x&&r==y){  //范围符合,v数组进行标记
        v[k]+=t;    
        return ;
    }
  //继续寻找
    f[k]+=(y-x+1)*t;   //对属于范围内的元素进行加法运算
    int m=(l+r)>>1; 
  //将区间一分为二
    if(y<=m)  
        in(k+k,l,m,x,y,t);
     //查询区间右边界<=当前区间左儿子右边界,
     //查询区间∈当前区间左儿子
    else  
    if(x>m)
       in(k+k+1,m+1,r,x,y,t);
     //查询区间左边界>=当前区间右儿子左边界,
     //查询区间∈当前区间右儿子
    else 
        in(k+k+1,m+1,r,m+1,y,t),in(k+k,l,m,x,m,t);
       //否则递归两边区间
}

至此我们便可以对区间进行范围性加法操作,
但要如何查询呢
当我们要查询1-3的区间和时,
发现(1-3)不完全∈(1-4),却可以发现其儿子(1-2),(3-4)中,都包含了查询区间,于是把查询区间分为两块,分别对(1-2),(3-4)进行查询(1-2),(3)
接着我们发现(1-2)∈(1-2),则返回答案,
(3)不完全∈(3-4),发现其左儿子包含了3,则递归左儿子,然后查询到了(3),便返回(3)

ll cal(int k,int l,int r,int a,int b,ll ans){
  //ans记录当前节点接受的值
    ans += v[k];
  //累计已标记的值
    if(l==a&&r==b){
        return 1LL*(f[k] + ans * (b - a + 1 ));
    //刚好查询到范围,返回当前区间和+标记值*区间范围
    }
    int m=(l+r)>>1;
    if(b<=m)return cal(k+k,l,m,a,b,ans);
       //查询区间右边界<=当前区间左儿子右边界,
      //查询区间∈当前区间左儿子
    else if(a>m)return cal(k+k+1,m+1,r,a,b,ans);
       //查询区间左边界>=当前区间右儿子左边界,
      //查询区间∈当前区间右儿子
    else 
    return cal(k+k,l,m,a,m,ans)+cal(k+k+1,m+1,r,m+1,b,ans);
         //否则递归两边区间
}

另外对于n个数的数组,把他递归分成一颗二叉搜索树,其的数组范围就是结点的数量,应该开到4n
洛谷原题1线段树加法
answer code:

#include <bits/stdc++.h>
#define rep(i,n,m) for(int i=n;i<=m;++i)
#define per(i,n,m) for(int i=n;i>=m;--i)
#define PII pair<int,int>
#define lowbit(x) x&-x
#define INF 1<<30
using namespace std;
typedef long long ll;
const int N=4e5+10;
int num[N];
ll f[N],v[N];
void build(int k,int l,int r){
    v[k]=0;
    if(l==r){
        f[k]=num[l];
        return ;
    }
    int m=(l+r)>>1;
    build(k+k,l,m);
    build(k+k+1,m+1,r);
    f[k]=f[k+1+k]+f[k+k];
}
void in(int k,int l,int r,int x,int y,ll t){
    if(l==x&&r==y){
        v[k]+=t;    
        return ;
    }
    f[k]+=(y-x+1)*t;
    int m=(l+r)>>1;
    if(y<=m)
        in(k+k,l,m,x,y,t);
    else  
    if(x>m)
       in(k+k+1,m+1,r,x,y,t);
    else 
        in(k+k+1,m+1,r,m+1,y,t),in(k+k,l,m,x,m,t);

}
ll cal(int k,int l,int r,int a,int b,ll ans){
    ans += v[k];
    if(l==a&&r==b){
        return 1LL*(f[k] + ans * (b - a + 1 ));
    }
    int m=(l+r)>>1;
    if(b<=m)return cal(k+k,l,m,a,b,ans);
    else if(a>m)return cal(k+k+1,m+1,r,a,b,ans);
    else 
    return cal(k+k,l,m,a,m,ans)+cal(k+k+1,m+1,r,m+1,b,ans);
}
int main()
{
    int n,m;cin>>n>>m;
    rep(i,1,n)cin>>num[i];
    build(1,1,n);
    while(m--){
        int t;cin>>t;
        if(t==1){
            int a,b;ll c;cin>>a>>b>>c;
            in(1,1,n,a,b,c);
        }
        else {
            int b,c;cin>>b>>c;
            cout<<cal(1,1,n,b,c,0)<<endl;
        }
    }
    return 0;
}

🥰🥰🥰😘
2022-9-7 23:24
待更新区间乘法….

太难啦太难啦,为什莫这么烦 QAQ
洛谷原题2线段树乘法

当我们需要对区间进行乘法操作和加法时,一个标记肯定不满足,所以需要另开一个数组标记该结点需要的乘数,并且这两种操作方法对于取模操作是不封闭的,每一次都可以取模运算。

此外我们需要用一个函数来维护区间内的标记,使得标记下传,对于题目给的加法和乘法操作,在下传标记的时候要么先加后乘,要么先乘后加,而我们采用的是先乘后加。()

//push维护标记下传

void push(int k,int l,int r){
    int m=(l+r)>>1;
    //维护节点权值
    //f[儿子]=(mul[父亲]*f[儿子]+add[父亲]*(区间长度))%模
    f[k+k]=(mul[k]*f[k+k]+add[k]*(m-l+1))%p;
    f[k+k+1]=(mul[k]*f[k+k+1]+add[k]*(r-m))%p;
    
    //维护乘法和加法后的值
    //mul[儿子]=(mul[父亲]*mul[儿子])%模
    mul[k+k]=(mul[k]*mul[k+k])%p;
    mul[k+k+1]=(mul[k]*mul[k+k+1])%p;

    //add[儿子]=(add[儿子]*mul[父亲]+add[父亲])%模
    add[k+k]=(add[k+k]*mul[k]+add[k])%p;
    add[k+k+1]=(add[k+k+1]*mul[k]+add[k])%p;
    
    //初始化标记
    mul[k]=1;
    add[k]=0;
    return ;
}

为了使得标记值每次都能往下传递,所以每次操作都应该用一次push
来保证标记传递和标记初始化
区间乘法,t表示乘上的数

    f[k]=(f[k]*t)%p;
    mul[k]=(mul[k]*t)%p;
    add[k]=(add[k]*t)%p;

区间加法

    add[k]=(add[k]+t)%p;
    f[k]=(f[k]+t*(r-l+1))%p;
#include <bits/stdc++.h>
#define rep(i,n,m) for(int i=n;i<=m;++i)
#define per(i,n,m) for(int i=n;i>=m;--i)
#define PII pair<int,int>
#define lowbit(x) x&-x
#define INF 1<<30
using namespace std;
typedef long long ll;
const int N=3e5+10;
ll num[N],f[N],add[N],mul[N],p;
void build(int k,int l,int r){
    add[k]=0;
    mul[k]=1;
    if(l==r){
        f[k]=num[l];
        f[k]%=p;
        return ;
    }
    int m=(l+r)>>1;
    build(k+k,l,m);
    build(k+k+1,m+1,r);
    f[k]=(f[k+1+k]+f[k+k])%p;
    //cout<<k<<' '<<f[k]<<endl;
}
void push(int k,int l,int r){
    int m=(l+r)>>1;
    f[k+k]=(mul[k]*f[k+k]+add[k]*(m-l+1))%p;
    f[k+k+1]=(mul[k]*f[k+k+1]+add[k]*(r-m))%p;
    //维护乘法和加法后的值
    mul[k+k]=(mul[k]*mul[k+k])%p;
    mul[k+k+1]=(mul[k]*mul[k+k+1])%p;

    add[k+k]=(add[k+k]*mul[k]+add[k])%p;
    add[k+k+1]=(add[k+k+1]*mul[k]+add[k])%p;
    //维护乘法加法的值
    mul[k]=1;
    add[k]=0;
    //初始化
    return ;
}
//乘法操作
void in1(int k,int l,int r,int x,int y,ll t){
    if(y<l||x>r) return ;

    if(x<=l&r<=y){
        f[k]=(f[k]*t)%p;
        mul[k]=(mul[k]*t)%p;
        add[k]=(add[k]*t)%p;
        return ;
    }

    push(k,l,r);
    int m=(l+r)>>1;
    in1(k+k,l,m,x,y,t);
    in1(k+k+1,m+1,r,x,y,t);
    f[k]=(f[k+k+1]+f[k+k])%p;
    return ;
}
//加法操作
void in2(int k,int l,int r,int x,int y,ll t){
    if(y<l||x>r) return ;

    if(x<=l&&r<=y){
        add[k]=(add[k]+t)%p;
        f[k]=(f[k]+t*(r-l+1))%p;
        return ;
    }

    push(k,l,r);
    int m=(l+r)>>1;
    in2(k+k,l,m,x,y,t);
    in2(k+k+1,m+1,r,x,y,t);
    f[k]=(f[k+k+1]+f[k+k])%p;
    return ;
}
//计算区间和
ll cal(int k,int l,int r,int a,int b){
    if(b<l||a>r) return 0;

    if(a<=l&&r<=b){
        return f[k];
    }

    push(k,l,r);
    int m=(l+r)>>1;
    return (cal(k+k,l,m,a,b)+cal(k+k+1,m+1,r,a,b))%p;
}
int main()
{
    int n,m;cin>>n>>m>>p;
    rep(i,1,n)cin>>num[i];
    build(1,1,n);
    while(m--){
        int t;cin>>t;
        if(t==1){
            int a,b;ll c;cin>>a>>b>>c;
            in1(1,1,n,a,b,c);
        }else if(t==2){
            int a,b;ll c;cin>>a>>b>>c;
            in2(1,1,n,a,b,c);
        }
        else {
            int b,c;cin>>b>>c;
            cout<<cal(1,1,n,b,c)<<endl;
        }
    }
    return 0;
}

差不多吧,总觉得还是有个点不是很透彻,慢慢悟吧
2022-9-8 19:54

微博摸张长图