题目描述

给定一个长度为N的数列A，以及M条指令，每条指令可能是以下两种之一：
1、“C l r d”，表示把 A[l],A[l+1],…,A[r] 都加上 d。
2、“Q l r”，表示询问 数列中第 l~r 个数的和。
对于每个询问，输出一个整数表示答案。

输入格式

第一行两个整数N,M。
第二行N个整数A[i]。
接下来M行表示M条指令，每条指令的格式如题目描述所示。

输出格式

对于每个询问，输出一个整数表示答案。
每个答案占一行。

说点什么

这题是树状数组的板子题当然也是线段树的板子题，不过好像没有人写线段树的题解（也可能我没发现
对于线段树，lazytag是个神奇的东西

线段树代码

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=1e5+10;
int n,m;
int a[N];
struct node
{
    int l,r;
    ll v,lazy;
}tree[N*4];
void pushup(int u)
{
    tree[u].v=tree[u<<1].v+tree[u<<1|1].v;
}
void build(int u,int l,int r)
{
    tree[u]={l,r};
    if(l==r) 
    {
        tree[u].v=a[l];
        return;
    }
    int mid=l+r>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    pushup(u);
}
void pushdown(int u)
{
    if(tree[u].lazy)
    {
        int lazy=tree[u].lazy;
        tree[u<<1].lazy+=lazy;
        tree[u<<1|1].lazy+=lazy;
        tree[u<<1].v+=lazy*(tree[u<<1].r-tree[u<<1].l+1);
        tree[u<<1|1].v+=lazy*(tree[u<<1|1].r-tree[u<<1|1].l+1);
        tree[u].lazy=0;
    }
}
void modify(int u,int l,int r,int v)
{
    if(tree[u].l>=l&&tree[u].r<=r)
    {
        tree[u].lazy+=v;
        tree[u].v+=(tree[u].r-tree[u].l+1)*v;
        return;
    }
    pushdown(u);//下传懒标记
    int mid=tree[u].r+tree[u].l>>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(tree[u].l>=l&&tree[u].r<=r) return tree[u].v;

    pushdown(u);
    int mid=tree[u].l+tree[u].r>>1;
    ll v=0;
    if(l<=mid) v=query(u<<1,l,r);
    if(r>mid) v+=query(u<<1|1,l,r);
    return v;
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    while(m--)
    {
        char op;
        cin>>op;
        if(op=='C')
        {
            int l,r,d;
            cin>>l>>r>>d;
            modify(1,l,r,d);
        }
        else
        {
            int l,r;
            cin>>l>>r;
            cout<<query(1,l,r)<<endl;
        }
    }
    return 0;
}

分块代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=100010;
typedef long long ll;
int n,m;
ll a[N],res[N],base[N];
int sz;
ll query(int l,int r)
{
    int idl=l/sz,idr=r/sz;
    ll ans=0;
    if(idl==idr)
        for(int i=l;i<=r;i++) ans+=base[idl]+a[i];
    else
    {
        for(int i=l;i<(idl+1)*sz;i++) ans+=base[idl]+a[i];
        for(int i=idl+1;i<idr;i++) ans+=res[i];
        for(int i=idr*sz;i<=r;i++) ans+=base[idr]+a[i];
    }
    return ans;
}
void change(int l,int r,int x)
{
    int idl=l/sz,idr=r/sz;
    if(idl==idr)
        for(int i=l;i<=r;i++)
        {
            a[i]+=x;
            res[idl]+=x;
        }
    else
    {
        for(int i=l;i<(idl+1)*sz;i++) 
        {
            a[i]+=x;
            res[idl]+=x;
        }
        for(int i=idl+1;i<idr;i++) 
        {
            base[i]+=x;
            res[i]+=1ll*x*sz;
        }
        for(int i=idr*sz;i<=r;i++)
        {
            a[i]+=x;
            res[idr]+=x;
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    sz=sqrt(n);
    for(int i=1;i<=n;i++) 
    {
        scanf("%lld",&a[i]);
        res[i/sz]+=a[i];
    }
    char op;
    int l,r,x;
    while(m--)
    {
        cin>>op>>l>>r;
        if(op=='Q') printf("%lld\n",query(l,r));
        else
        {
            scanf("%d",&x);
            change(l,r,x);
        }
    }
    return 0;

}