C02【模板】线段树+懒标记 P3372 线段树 1

// 线段树 O(mlogn) 数组版 I LOVE
#include<bits/stdc++.h>
using namespace std;

#define int long long
#define N 1000005
int n,m,w[N],op,x,y,k;

struct SGT{ //线段树
  #define lc (u<<1)
  #define rc (u<<1|1)
  #define mid (l+r>>1)
  int sum[N*4],add[N*4]; //区间和,懒标记
  
  void pushup(int u){
    sum[u]=sum[lc]+sum[rc];
  }
  void pushdown(int u,int l,int r,int m){
    if(add[u]){
      sum[lc]+=add[u]*(m-l+1);
      sum[rc]+=add[u]*(r-m);
      add[lc]+=add[u];
      add[rc]+=add[u];
      add[u]=0;
    }
  }
  void build(int u=1,int l=1,int r=n){
    if(l==r){sum[u]=w[l]; return;}
    build(lc,l,mid); 
    build(rc,mid+1,r);
    pushup(u);
  }
  void upd(int x,int y,int k,int u=1,int l=1,int r=n){ //区修
    if(x>r || y<l) return; //越界
    if(x<=l && r<=y){      //覆盖即返回
      sum[u]+=(r-l+1)*k;
      add[u]+=k;
      return;
    }
    pushdown(u,l,r,mid);    
    upd(x,y,k,lc,l,mid); //裂开
    upd(x,y,k,rc,mid+1,r);
    pushup(u);
  }
  int ask(int x,int y,int u=1,int l=1,int r=n){ //区查
    if(x>r || y<l) return 0;
    if(x<=l && r<=y) return sum[u];
    pushdown(u,l,r,mid);
    return ask(x,y,lc,l,mid)+ask(x,y,rc,mid+1,r);
  }
}S;

signed main(){
  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  cin>>n>>m;
  for(int i=1; i<=n; i++) cin>>w[i];
  S.build();
  while(m--){
    cin>>op>>x>>y;
    if(op==1) cin>>k,S.upd(x,y,k);
    else cout<<S.ask(x,y)<<"\n";
  }
}

疑似分块：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10,M=2010;
int a[N],s[M],tag[M],siz[M],n,B;
void change(int l,int r,int k)
{
	int bl=(l-1)/B+1,br=(r-1)/B+1;
	if(bl==br)
	{
		s[bl]+=(r-l+1)*k;
		for(int i=l;i<=r;i++)a[i]+=k;
	}
	else
	{
		s[bl]+=(bl*B-l+1)*k;
		s[br]+=(r-(br-1)*B)*k;
		for(int i=l;i<=bl*B;i++)a[i]+=k;
		for(int i=(br-1)*B+1;i<=r;i++)a[i]+=k;
		for(int i=bl+1;i<=br-1;i++)s[i]+=siz[i]*k,tag[i]+=k;
	}
}
int query(int l,int r)
{
	int bl=(l-1)/B+1,br=(r-1)/B+1,ans=0;
	if(bl==br)
	{
		for(int i=l;i<=r;i++)ans+=a[i];
		ans+=(r-l+1)*tag[bl];
	}
	else
	{
		for(int i=l;i<=bl*B;i++)ans+=a[i];
		for(int i=(br-1)*B+1;i<=r;i++)ans+=a[i];
		ans+=tag[bl]*(bl*B-l+1),ans+=tag[br]*(r-(br-1)*B);
		for(int i=bl+1;i<=br-1;i++)ans+=s[i];
	}
	return ans;
}
signed main()
{
	int n,q;cin>>n>>q;B=sqrt(n);
	for(int i=1;i<=n;i++)cin>>a[i],s[(i-1)/B+1]+=a[i],siz[(i-1)/B+1]++;
	while(q--)
	{
		int op,l,r;cin>>op>>l>>r;
		if(op==1)
		{
			int k;cin>>k;
			change(l,r,k);
		}
		else
		{
			cout<<query(l,r)<<'\n';
		}
	}
	return 0;
}

#include<algorithm>
#include<cstdio>
#include<cmath>
#define ll long long
#define MaxN 1110000
using namespace std;
int BS;
ll a[MaxN],tag[1005],sum[1005];
void add(int l,int r,ll x)
{
  int bl=l/BS,br=r/BS;
  if (bl==br){
    for (int i=l;i<=r;i++)a[i]+=x;
    sum[bl]+=(r-l+1)*x;
  }else{
    sum[bl]+=(bl*BS+BS-l)*x;
    sum[br]+=(r-br*BS+1)*x;
    for (int i=l;i<bl*BS+BS;i++)a[i]+=x;
    for (int i=br*BS;i<=r;i++)a[i]+=x;
    for (int i=bl+1;i<br;i++){sum[i]+=BS*x;tag[i]+=x;}
  }
}
ll qry(int l,int r)
{
  int bl=l/BS,br=r/BS;
  if (bl==br){
    ll ans=(r-l+1)*tag[bl];
    for (int i=l;i<=r;i++)ans+=a[i];
    return ans;
  }else{
    ll ans=(bl*BS+BS-l)*tag[bl]
          +(r-br*BS+1)*tag[br];
    for (int i=l;i<bl*BS+BS;i++)ans+=a[i];
    for (int i=br*BS;i<=r;i++)ans+=a[i];
    for (int i=bl+1;i<br;i++)ans+=sum[i];
    return ans;
  }
}
int n,m;
int main()
{
  scanf("%d%d",&n,&m);
  BS=sqrt(n)+1;
  for (int i=0;i<n;i++){
    scanf("%lld",&a[i]);
    sum[i/BS]+=a[i];
  }
  for (int i=0,op,l,r;i<m;i++){
    scanf("%d%d%d",&op,&l,&r);
    l--;r--;
    if (op==1){
      ll x;scanf("%lld",&x);
      add(l,r,x);
    }else printf("%lld\n",qry(l,r));
  }return 0;
}

C79 线段树+标记永久化 区修+区查 Luogu P3372 线段树 1
C82 树状数组 区修+区查 Luogu P3372 线段树 1

/*
区查推导：
1到r的区间和
a[1] +a[2] + ...+ a[r]
= d[1] + (d[1] + d[2]) + ... + (d[1] + d[2] + ... + d[r])
=(d[1]*r) +(d[2]*(r - 1))+ ... + (d[r]* 1)
=(d[1] + d[2] +...+ d[r])*r-(d[1]*0 +d[2]*1+...+ d[r]*(r -1))
开两颗树状数组:用c1维护 d[i]，用c2维护d[i]* (i-1)
*/
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL N=1e6+10;
LL n,a[N],c1[N],c2[N];
void add(LL c[],LL x,LL k){for(;x<=n;x+=x&-x)c[x]+=k;}
LL sum(LL c[],LL x){LL res=0;for(;x>=1;x-=x&-x)res+=c[x];return res;}
LL getsum(LL x){ return sum(c1,x)*x-sum(c2,x); }
int main()
{
    LL m;scanf("%lld%lld",&n,&m);
    memset(c1,0,sizeof(c1));
    memset(c2,0,sizeof(c2));
    a[0]=0;for(LL i=1;i<=n;i++)scanf("%lld",&a[i]);
    for(LL i=1;i<=n;i++)
    {
        LL d=a[i]-a[i-1];
        add(c1,i,d);
        add(c2,i,d*(i-1));
    }
    for(LL i=1,op,x,y,d;i<=m;i++)
    {
        scanf("%lld",&op);
        if(op==1)
        {
            scanf("%lld%lld%lld",&x,&y,&d);
            add(c1,x,d);        add(c1,y+1,-d);
            add(c2,x,d*(x-1));  add(c2,y+1,-d*y);
        }
        else
        {
            scanf("%lld%lld",&x,&y);
            printf("%lld\n", getsum(y)-getsum(x-1) );
        }
    }
    return 0;
}