#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
struct node{
int l,r;
long long lazy;
long long val;
};
node tree[N<<2];
int n,a[N];
int q;
void spread(int p,long long tag){
int lt=tree[p].l;
int rt=tree[p].r;
tree[p].val+=tag*(rt-lt+1);
tree[p].lazy+=tag;
}
void push_down(int p){
long long tag=tree[p].lazy;
if(!tag) return ;
spread(p<<1,tag);
spread(p<<1|1,tag);
tree[p].lazy=0;
}
void push_up(int p){
tree[p].val=tree[p<<1].val+tree[p<<1|1].val;
}
void build(int p, int L, int R){
tree[p].l=L , tree[p].r=R;
if(L==R){
tree[p].val=a[L];
return ;
}
int mid =(L+R)>>1;
build(p<<1,L,mid);
build(p<<1|1,mid+1,R);
push_up(p);
}
long long query(int p,int L,int R){
int lt=tree[p].l , rt=tree[p].r;
if(L<=lt && rt<=R)
return tree[p].val;
long long sum=0;
push_down(p);
int mid=(lt+rt)>>1;
if(mid>=L)
sum+=query(p<<1,L,R);
if(mid<R)
sum+=query(p<<1|1,L,R);
return sum;
}
void change(int p,int L,int R,int x){
int lt=tree[p].l , rt=tree[p].r;
if(L<=lt && rt<=R){
spread(p,x);
return ;
}
push_down(p);
int mid=(lt+rt)>>1;
if(mid>=L)
change(p<<1,L,R,x);
if(R>mid)
change(p<<1|1,L,R,x);
push_up(p);
}
int main(){
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
build(1,1,n);
while(q--){
int ch;
scanf("%d",&ch);
if(ch==1){
int fr,st,x;
scanf("%d%d%d",&fr,&st,&x);
change(1,fr,st,x);
}
else{
int fr,st;
scanf("%d%d",&fr,&st);
printf("%lld\n",query(1,fr,st));
}
}
}
线段树
2023-01-07 16:20:42 By huangxuan
新博客
2022-08-15 10:06:18 By huangxuan
新博客
2022-06-15 17:47:34 By huangxuan
ubc26.github.io
新博客
2022-06-12 16:31:53 By huangxuan
42页嗨嗨嗨
2022-05-27 20:21:07 By huangxuan