线段树模板存档
2026-01-30 13:04:00
发布于：广东
8阅读
0回复
0点赞
Problem
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 100009
#define lc 2*i
#define rc lc+1
int n,m;
int a[N];
int tr[N*4],tag[N*4];
void pushup(int i){
tr[i] = tr[lc]+tr[rc];
}
void build(int i,int l,int r){
if(l == r){
tr[i] = a[l];
return ;
}
int mid = l+r>>1;
build(lc,l,mid);
build(rc,mid+1,r);
pushup(i);
}
void addtag(int i,int l,int r,int k){
tag[i]+=k;
tr[i]+=(r-l+1)*k;
}
void downtag(int i,int l,int r){
tag[lc]+=tag[i];
tag[rc]+=tag[i];
tr[lc]+=tag[i]*l;
tr[rc]+=tag[i]*r;
tag[i] = 0;
}
void update(int i,int l,int r,int ql,int qr,int k){
if(qr<l||ql>r) return ;
if(ql<=l&&r<=qr){
addtag(i,l,r,k);
return ;
}
int mid = l+r>>1;
downtag(i,mid-l+1,r-mid);
update(lc,l,mid,ql,qr,k);
update(rc,mid+1,r,ql,qr,k);
pushup(i);
}
int query(int i,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr) return tr[i];
int mid = l+r>>1;
downtag(i,mid-l+1,r-mid);
int ans = 0;
if(ql<=mid) ans+=query(lc,l,mid,ql,qr);
if(qr>mid) ans+=query(rc,mid+1,r,ql,qr);
return ans;
}
signed main(){
cin>>n>>m;
for(int i = 1;i<=n;++i){
cin>>a[i];
}
build(1,1,n);
for(int i = 1;i<=m;++i){
int op;
cin>>op;
if(op == 1){
int x,y,k;
cin>>x>>y>>k;
update(1,1,n,x,y,k);
}else{
int x,y;
cin>>x>>y;
cout<<query(1,1,n,x,y)<<'\n';
}
}
}
有帮助，赞一个