区间历史版本和板子
cpp
struct SegmentTree{
int ts=0;
struct Node{
// c=ans-a*ts,ans=c+a*ts
int c,a,len,addc,adda;
};
vector<Node> t;
void init(int n){
t=vector<Node>(n<<2);
}
void pushup(int p){
t[p].c=t[p<<1].c+t[p<<1|1].c;
t[p].a=t[p<<1].a+t[p<<1|1].a;
}
void pushtag(int p,int addc,int adda){
t[p].c+=addc*t[p].len;
t[p].a+=adda*t[p].len;
t[p].addc+=addc;
t[p].adda+=adda;
}
void pushdown(int p){
if(t[p].adda||t[p].addc){
pushtag(p<<1,t[p].addc,t[p].adda);
pushtag(p<<1|1,t[p].addc,t[p].adda);
t[p].addc=0;
t[p].adda=0;
}
}
void build(int p,int l,int r,vector<int> &a){
t[p]={0,0,r-l+1,0,0};
if(l==r){
t[p].a=a[l];
return;
}
int mid=l+r>>1;
build(p<<1,l,mid,a);
build(p<<1|1,mid+1,r,a);
pushup(p);
}
void modify(int p,int l,int r,int ql,int qr,int x){
if(ql<=l&&r<=qr){
pushtag(p,-ts*x,x);
return;
}
pushdown(p);
int mid=l+r>>1;
if(ql<=mid)modify(p<<1,l,mid,ql,qr,x);
if(qr>mid)modify(p<<1|1,mid+1,r,ql,qr,x);
pushup(p);
}
int query(int p,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr)return t[p].c+t[p].a*ts;
pushdown(p);
int res=0,mid=l+r>>1;
if(ql<=mid)res+=query(p<<1,l,mid,ql,qr);
if(qr>mid)res+=query(p<<1|1,mid+1,r,ql,qr);
return res;
}
void upd(){ts++;}
} t;
void solve(){
int n,m;
cin>>n>>m;
t.init(n);
vector<int> a(n+1);
for(int i=1;i<=n;i++)cin>>a[i];
t.build(1,1,n,a);
t.ts=1;
while(m--){
int op,l,r,x;
cin>>op>>l>>r;
if(op==1){
cin>>x;
t.modify(1,1,n,l,r,x);
}
else{
cout<<t.query(1,1,n,l,r)<<"\n";
}
t.upd();
}
}