Segment Tree线段树

题目描述#

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

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

输入格式#

第一行包含两个整数，分别表示该数列数字的个数和操作的总个数。

第二行包含个用空格分隔的整数，其中第个数字表示数列第项的初始值。

接下来行每行包含或个整数，表示一个操作，具体如下：

1 x y k：将区间内每个数加上。
2 x y：输出区间内每个数的和。

输出格式#

输出包含若干行整数，即为所有操作 2 的结果。

样例 #1#

样例输入 #1#

plaintext

样例输出 #1#

11
8
20

plaintext

提示#

对于的数据：，。
对于的数据：，。
对于的数据：。

保证任意时刻数列中任意元素的和在内。

【样例解释】

算法分析
模板-区间和
模板-区间乘余mod

{% raw %}

{% endraw %}

建树#

void build(int pos,int l,int r){
    tree[pos].l=l,tree[pos].r=r;
    if(l==r) {tree[pos].val=read()%mod;return;}
    int mid=(l+r)>>1;
    build(pos<<1,l,mid);
    build(pos<<1|1,mid+1,r);
    pushup(pos);
}

cpp

上放#

void pushup(int pos){
    tree[pos].val=(tree[pos<<1].val+tree[pos<<1|1].val)%mod;
}

cpp

下放#

和#

void pushdown(int pos){
    if(tree[pos].lazy){
        tree[pos<<1].val+=tree[pos].lazy*(tree[pos<<1].r-tree[pos<<1].l+1);
        tree[pos<<1|1].val+=tree[pos].lazy*(tree[pos<<1|1].r-tree[pos<<1|1].l+1);
        tree[pos<<1].lazy+=tree[pos].lazy;
        tree[pos<<1|1].lazy+=tree[pos].lazy;
        tree[pos].lazy=0;
    }
    return;
}

cpp

和与积#

void pushdown(int pos){
    if(tree[pos].lazy||tree[pos].mu!=1){
        tree[pos<<1].mu=(tree[pos<<1].mu*tree[pos].mu)%mod;
		tree[pos<<1|1].mu=(tree[pos<<1|1].mu*tree[pos].mu)%mod;
		tree[pos<<1].lazy=(tree[pos<<1].lazy*tree[pos].mu)%mod;
		tree[pos<<1|1].lazy=(tree[pos<<1|1].lazy*tree[pos].mu)%mod;
		tree[pos<<1].val=(tree[pos<<1].val*tree[pos].mu)%mod;
		tree[pos<<1|1].val=(tree[pos<<1|1].val*tree[pos].mu)%mod;
		tree[pos].mu=1;
		tree[pos<<1].val=(tree[pos<<1].val+tree[pos].lazy*(tree[pos<<1].r-tree[pos<<1].l+1))%mod;
		tree[pos<<1|1].val=(tree[pos<<1|1].val+tree[pos].lazy*(tree[pos<<1|1].r-tree[pos<<1|1].l+1))%mod;
		tree[pos<<1].lazy=(tree[pos].lazy+tree[pos<<1].lazy)%mod;
		tree[pos<<1|1].lazy=(tree[pos].lazy+tree[pos<<1|1].lazy)%mod;
		tree[pos].lazy=0;
    }
}

cpp

更新#

单点更新（加）#

void updatepoint(int pos,int x,int data){
    if(tree[pos].l==x&&tree[pos].r==x) tree[pos].val+=data;
    pushdown(pos);
    int mid=(tree[pos].l+tree[pos].r)>>1;
    if(mid<x) updatepoint(pos<<1|1,x,data);
    else updatepoint(pos<<1,x,data);
    pushup(pos);
}

cpp

区间更新#

和#

void updatarea_add(int pos,int x,int y,int data){
    int l = tree[pos].l,r=tree[pos].r;
    int len=r-l+1,mid=(l+r)>>1;
    if(l>=x&&r<=y){
        tree[pos].val+=len*data;
        tree[pos].lazy+=data;
        return;
    }
    pushdown(pos);
    if(mid>=x) updatarea_add(pos<<1,x,y,data);
    if(mid<y) updatarea_add(pos<<1|1,x,y,data);
    pushup(pos);
}

cpp

积#

void updatearea_acu(int pos,int x,int y,int data){
    int l = tree[pos].l,r=tree[pos].r;
    int mid=(l+r)>>1;
    if(l>=x&&r<=y){
        tree[pos].val=(tree[pos].val*data)%mod;
        tree[pos].lazy=(tree[pos].lazy*data)%mod;
        tree[pos].mu=(tree[pos].mu*data)%mod;
        return;
    }
    pushdown(pos);
    if(mid>=x) updatearea_acu(pos<<1,x,y,data);
    if(mid<y) updatearea_acu(pos<<1|1,x,y,data);
    pushup(pos);
}

cpp

查询#

单点查询#

int querypoint(int pos,int x){
    if(tree[pos].l==x&&tree[pos].r==x) return tree[pos].val;
    pushdown(pos);
    int mid=(tree[pos].l+tree[pos].r)>>1;
    if(mid<x) return querypoint(pos<<1|1,x);
    else return querypoint(pos<<1,x);
}

cpp

区间和查询#

long long queryarea(int x,int y,int pos){
    int l = tree[pos].l,r=tree[pos].r;
    if(x<=l&&r<=y) return tree[pos].val;
    pushdown(pos);
    int mid=(l+r)>>1;
    long long ans=0;
    if(mid>=x) ans=(ans+queryarea(x,y,pos<<1))//%mod;<--按需
    if(mid<y) ans=(ans+queryarea(x,y,pos<<1|1))//%mod;<--按需
    return ans;
}

cpp

{% raw %}

{% endraw %}

{% raw %}

{% endraw %}

#include<iostream>
using namespace std;
int a[100005];
struct node{
    int l;
    int r;
    long long val;
    int lazy;
}tree[6000005];
inline long long read(){
	long long x=0,f=1;char c=getchar();
	for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
	for(;isdigit(c);c=getchar())x=(x<<3)+(x<<1)+(c^48);
	return x*f;
}
void pushup(int pos){
    tree[pos].val=tree[pos<<1].val+tree[pos<<1|1].val;
}
void pushdown(int pos){
    if(tree[pos].lazy){
        tree[pos<<1].val+=tree[pos].lazy*(tree[pos<<1].r-tree[pos<<1].l+1);
        tree[pos<<1|1].val+=tree[pos].lazy*(tree[pos<<1|1].r-tree[pos<<1|1].l+1);
        tree[pos<<1].lazy+=tree[pos].lazy;
        tree[pos<<1|1].lazy+=tree[pos].lazy;
        tree[pos].lazy=0;
    }
    return;
}
void updata(int pos,int l,int r,int data){
    if(tree[pos].l>=l&&tree[pos].r<=r){
        tree[pos].val+=((tree[pos].r-tree[pos].l+1)*data);
        tree[pos].lazy+=data;
        return;
    }
    pushdown(pos);
    int mid=(tree[pos].l+tree[pos].r)>>1;
    if(mid>=l) updata(pos<<1,l,r,data);
    if(mid<r) updata(pos<<1|1,l,r,data);
    pushup(pos);
}
long long query(int x,int y,int pos){
    pushdown(pos);
    if(x<=tree[pos].l&&y>=tree[pos].r) return tree[pos].val;
    int mid=(tree[pos].l+tree[pos].r)>>1;
    long long ans=0;
    if(mid>=x)ans+=query(x,y,pos<<1);
    if(mid<y)ans+=query(x,y,pos<<1|1);
    return ans;
}
void build(int pos,int l,int r){
    tree[pos].l=l,tree[pos].r=r;
    if(l==r){
        tree[pos].val=read();
        return;
    }
    int mid=(l+r)>>1;
    build(pos<<1,l,mid);
    build(pos<<1|1,mid+1,r);
    pushup(pos);
    return;
}
int main(){
    int n,m,opt,x,y,k;
    cin>>n>>m;
    build(1,1,n);
    for(int i = 1;i<=m;i++){
        cin>>opt;
        if(opt==1){
            cin>>x>>y>>k;
            updata(1,x,y,k);
        }else{
            cin>>x>>y;
            cout<<query(x,y,1)<<endl;
        }
    }
}

cpp

{% raw %}

{% endraw %}

{% raw %}

{% endraw %}

#

#include<iostream>
using namespace std;
int mod;
int a[100005];
struct node{
    int l;
    int r;
    long long val;
    long long lazy;
    long long mu=1;
}tree[400005];
inline long long read(){
	long long x=0,f=1;char c=getchar();
	for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
	for(;isdigit(c);c=getchar())x=(x<<3)+(x<<1)+(c^48);
	return x*f;
}
void pushup(int pos){
    tree[pos].val=(tree[pos<<1].val+tree[pos<<1|1].val)%mod;
}
void pushdown(int pos){
    if(tree[pos].lazy||tree[pos].mu!=1){
        tree[pos<<1].mu=(tree[pos<<1].mu*tree[pos].mu)%mod;
		tree[pos<<1|1].mu=(tree[pos<<1|1].mu*tree[pos].mu)%mod;
		tree[pos<<1].lazy=(tree[pos<<1].lazy*tree[pos].mu)%mod;
		tree[pos<<1|1].lazy=(tree[pos<<1|1].lazy*tree[pos].mu)%mod;
		tree[pos<<1].val=(tree[pos<<1].val*tree[pos].mu)%mod;
		tree[pos<<1|1].val=(tree[pos<<1|1].val*tree[pos].mu)%mod;
		tree[pos].mu=1;
		tree[pos<<1].val=(tree[pos<<1].val+tree[pos].lazy*(tree[pos<<1].r-tree[pos<<1].l+1))%mod;
		tree[pos<<1|1].val=(tree[pos<<1|1].val+tree[pos].lazy*(tree[pos<<1|1].r-tree[pos<<1|1].l+1))%mod;
		tree[pos<<1].lazy=(tree[pos].lazy+tree[pos<<1].lazy)%mod;
		tree[pos<<1|1].lazy=(tree[pos].lazy+tree[pos<<1|1].lazy)%mod;
		tree[pos].lazy=0;
    }
}
void update_add(int pos,int x,int y,int data){
    int l = tree[pos].l,r=tree[pos].r;
    int len=r-l+1,mid=(l+r)>>1;
    if(l>=x&&r<=y){
        tree[pos].val+=len*data;
        tree[pos].lazy+=data;
        return;
    }
    pushdown(pos);
    if(mid>=x) update_add(pos<<1,x,y,data);
    if(mid<y) update_add(pos<<1|1,x,y,data);
    pushup(pos);
}
void update_acu(int pos,int x,int y,int data){
    int l = tree[pos].l,r=tree[pos].r;
    int mid=(l+r)>>1;
    if(l>=x&&r<=y){
        tree[pos].val=(tree[pos].val*data)%mod;
        tree[pos].lazy=(tree[pos].lazy*data)%mod;
        tree[pos].mu=(tree[pos].mu*data)%mod;
        return;
    }
    pushdown(pos);
    if(mid>=x) update_acu(pos<<1,x,y,data);
    if(mid<y) update_acu(pos<<1|1,x,y,data);
    pushup(pos);
}
long long query(int x,int y,int pos){
    int l = tree[pos].l,r=tree[pos].r;
    if(x<=l&&r<=y) return tree[pos].val;
    pushdown(pos);
    int mid=(l+r)>>1;
    long long ans=0;
    if(mid>=x) ans=(ans+query(x,y,pos<<1))%mod;
    if(mid<y) ans=(ans+query(x,y,pos<<1|1))%mod;
    return ans;
}
void build(int pos,int l,int r){
    tree[pos].l=l,tree[pos].r=r;
    if(l==r) {tree[pos].val=read()%mod;return;}
    int mid=(l+r)>>1;
    build(pos<<1,l,mid);
    build(pos<<1|1,mid+1,r);
    pushup(pos);
}
int main(){
    int n,m,opt,x,y,k;
    cin>>n>>m>>mod;
    build(1,1,n);
    for(int i = 1;i<=m;i++){
        cin>>opt;
        if(opt==1){
            cin>>x>>y>>k;
            update_acu(1,x,y,k);
        }else if(opt==2){
            cin>>x>>y>>k;
            update_add(1,x,y,k);
        }else{
            cin>>x>>y;
            cout<<query(x,y,1)<<endl;
        }
    }
}

cpp

{% raw %}

{% endraw %}

题目描述#

输入格式#

输出格式#

样例 #1#

样例输入 #1#

样例输出 #1#

提示#

建树#

上放#

下放#

和#

和与积#

更新#

单点更新（加）#

区间更新#

和#

积#

查询#

单点查询#

区间和查询#

#

Comments