lb2003的个人博客

线段树打个$lazy$操作完美解决。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define gc getchar()
#define ll long long
using namespace std;
const int N=1e5+5;
template<class lb>
inline void qr(lb &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(ll x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
ll a[N];
struct Seg{int l,r;ll s,ad;}t[N<<2];
void pushdown(int p)
{
    if(t[p].ad)
    {
        ll &ad=t[p].ad;
        t[p<<1].s+=ad*(t[p<<1].r-t[p<<1].l+1);
        t[p<<1|1].s+=ad*(t[p<<1|1].r-t[p<<1|1].l+1);
        t[p<<1].ad+=ad;
        t[p<<1|1].ad+=ad;
        ad=0;
    }
}
void build(int p,int l,int r)
{
    t[p].l=l,t[p].r=r;
    if(l==r){t[p].s=a[l];return ;}
    int mid=l+r>>1;build(p<<1,l,mid),build(p<<1|1,mid+1,r);
    t[p].s=t[p<<1].s+t[p<<1|1].s;
}
void change(int p,int ql,int qr,ll ad)
{
    if(ql<=t[p].l&&qr>=t[p].r){t[p].ad+=ad;t[p].s+=ad*(t[p].r-t[p].l+1);return ;}
    int mid=t[p].l+t[p].r>>1;
    pushdown(p);
    if(ql<=mid)change(p<<1,ql,qr,ad);
    if(qr>mid)change(p<<1|1,ql,qr,ad);
    t[p].s=t[p<<1].s+t[p<<1|1].s;
}
ll query(int p,int ql,int qr)
{
    if(ql<=t[p].l&&qr>=t[p].r)return t[p].s;
    int mid=t[p].l+t[p].r>>1;
    pushdown(p);ll sum=0;
    if(ql<=mid)sum+=query(p<<1,ql,qr);
    if(qr>mid)sum+=query(p<<1|1,ql,qr);
    return sum;
}
int main()
{
    int n,m;qr(n),qr(m);
    for(int i=1;i<=n;i++)qr(a[i]);build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        char op[3];scanf("%s",op);
        if(op[0]=='C'){int l,r;ll d;qr(l),qr(r),qr(d);change(1,l,r,d);}
        else {int l,r;qr(l),qr(r);qw(query(1,l,r));puts("");}
    }
    return 0;
}

树状数组
难打，不建议。
因为树状数组时维护了一个差分，每一次只有修改$b[l],b[r+1]$
对前缀和的贡献就为$\sum_{i=1}^x\sum_{j=1}^i b[j]$
改写为:$\sum_{i=1}^x\sum_{j=1}^i b[j]=\sum_{i=1}^x (x+1)*b[i]-\sum_{i=1}^xi*b[i]$
开两个树状数组分别维护一下$b[i]$的前缀和与$i*b[i]$的前缀和即可。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#define ll long long 
#define gc getchar()
using namespace std;
const int N=1e5+5;
template<class o>
inline void qr(o &x)
{
    char c=gc;int f=1;x=0;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(ll x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
ll c[2][N],sum[N];int n;
inline void add(int k,int x,ll d){for(;x<=n;x+=x&-x)c[k][x]+=d;}
inline ll ask(int k,int x){ll ans=0;for(;x;x-=x&-x)ans+=c[k][x];return ans;}
int main()
{
    int m;qr(n),qr(m);
    for(int i=1;i<=n;i++)qr(sum[i]),sum[i]+=sum[i-1];
    for(int i=1;i<=m;i++)
    {
        char op[3];int l,r;ll d;scanf("%s",op);
        if(op[0]=='Q')qr(l),qr(r),qw(sum[r]+(r+1)*ask(0,r)-ask(1,r)-sum[l-1]-l*ask(0,l-1)+ask(1,l-1)),puts("");
        else qr(l),qr(r),qr(d),add(0,l,d),add(0,r+1,-d),add(1,l,l*d),add(1,r+1,-(r+1)*d);
    }
    return 0;
}