#线段树 #algorithm
cpp
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cout << #x << " = " << x << endl;
#define lowbit(x) (x & -x)
const int N = 1e5;
const int INF = 1e9;
typedef long long LL;
typedef pair<int, int> PII;
// typedef __int128 LL;
struct node{
int l,r;
LL add;
LL sm;
}tr[N*4+10];
int n,m;
int a[N];
void pushup(int u){
tr[u].sm=tr[u<<1].sm + tr[u<<1|1].sm;
}
void pushdown(int u){
node &root =tr[u],&left=tr[u<<1],&right=tr[u<<1|1];
if(root.add){
left.add += root.add,right.add += root.add;
left.sm+=(LL)root.add*(left.r-left.l+1);
right.sm+=(LL)root.add*(right.r-right.l+1);
root.add=0;
}
}
void build(int u,int l,int r){
if(l==r){
tr[u]={l,r,0,(LL)a[l]};
}
else{
tr[u]={l,r};
int mid = tr[u].l+tr[u].r>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
pushup(u);
}
}
void modify(int u,int l,int r,int v){
if(l<=tr[u].l && tr[u].r<=r){
tr[u].sm+= (LL)v*(tr[u].r-tr[u].l+1);
tr[u].add+=v;
return ;
}
else{
pushdown(u);
int mid = tr[u].l + tr[u].r>>1;
if(l<=mid) modify(u<<1,l,r,v);
if(r>mid) modify(u<<1|1,l,r,v);
pushup(u);
}
}
LL query(int u,int l,int r){
if(l<=tr[u].l && tr[u].r<=r){
return tr[u].sm;
}
else{
pushdown(u);
int mid = tr[u].l+tr[u].r>>1;
LL sm=0;
if(l<=mid) sm+= query(u<<1,l,r);
if(r>mid) sm+=query(u<<1|1,l,r);
// pushup(u);
return sm;
}
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
build(1,1,n);
while(m--){
int op,x,y,k;
cin>>op;
if(op==1){
cin>>x>>y>>k;
modify(1,x,y,k);
}
else{
cin>>x>>y;
cout<<query(1,x,y)<<endl;
}
}
return 0;
}
```cpp
#include<bits/stdc++.h>
using namespace std;
#define debug(x) cout<<#x<<" = "<<x<<endl;
// 线段树模板 无pushdown
const int N=5e5+5;
const int INF=0x3f3f3f;
struct tree{
int l,r,sm;
}tr[N*4+10];
int a[N];
int n,m;
void pushup(int u){
tr[u].sm=tr[u<<1].sm+tr[u<<1|1].sm;
}
void build(int u,int l,int r){
tr[u]={l,r};
if(l==r){
tr[u].sm=a[l];
return ;
}
else{
int mid = tr[u].l+tr[u].r>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
pushup(u);
}
}
int query(int u,int l,int r){
if(l<=tr[u].l && tr[u].r<=r){
return tr[u].sm;
}
int mid = tr[u].l + tr[u].r >>1;
int sm=0;
if(l<=mid) sm+=query(u<<1,l,r);
if(r>mid) sm+=query(u<<1|1,l,r);
return sm;
}
void modify(int u,int x,int v){
if(tr[u].l==tr[u].r){
tr[u].sm+=v;
return;
}
int mid = tr[u].l+tr[u].r>>1;
if(x<=mid) modify(u<<1,x,v);
else modify(u<<1|1,x,v);
pushup(u);
}
int main() {
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
build(1, 1, n);
while(m--){
int op,x,y;
cin>>op>>x>>y;
if(op==1){
modify(1,x,y);
}
else{
// cout<<"query"<<endl;
cout<<query(1,x,y)<<endl;
}
}
return 0;
}