题目描述

给定一个长度为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条指令，每条指令的格式如题目描述所示。

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

每个答案占一行。

数据范围
$1 \le N,M \le 10^5$,
$|d| \le 10000$,
$|A[i]| \le 1000000000$

样例

输入样例：
10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4
输出样例：
4
55
9
15

树状数组(区间修改+区间查询)

首先我们可以开一个数组B,然后对于每条C操作,我们直接利用前缀和的思想.

1. 把b[l]+=d;
2. 把b[r+1]-=d;

然后我们就成功达成成就,把维护序列的具体值,转化为维护指令的累计影响,每次操作的影响,在l处开始,然后在r+1处消除.然后就让单点修改可以维护区间修改.

现在b数组的前缀和就是$\sum_{i=1}^x b[i]$ 就是经过指令后a[x]增加的值,那么序列a的前缀和a[1~x]增加的值就是:

$$\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-i+1) \times b[i] = (x+1)\sum_{i=1}^x b[i] - \sum_{i=1}^x i \times b[i]$$

然后通过上面这个式子,我们就把原来的数组,经过差分操作去维护两个树状数组，一个维护$d_i$，一个维护$d_i \times i$这样的话,我们在区间修改的过程中,就可以在两个树状数组中去查询得到前缀和，然后同理,区间修改操作就是差分数组的修改,每次只需要修改两个点,完美的将区间再次转换为单调修改。

C++ 代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define lowbit(x) x&(-x)
const int N=2e5;
ll c1[N],c2[N],n,m,a[N];
ll add(ll x,ll y)
{
    for(ll i=x;i<=n;i+=lowbit(i))
    {
        c1[i]+=y;
        c2[i]+=x*y;
    }
}
ll ask(ll x)
{
    ll ans=0;
    for(ll i=x;i;i-=lowbit(i))
        ans+=(x+1)*c1[i]-c2[i];
    return ans;
}
int main()
{
    scanf("%lld%lld\n",&n,&m);
    for(ll i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        add(i,a[i]-a[i-1]);
    }
    getchar();
    while(m--)
    {
        char ch=getchar();
        if (ch=='Q')
        {
            ll x,y;
            scanf("%lld%lld\n",&x,&y);
            cout<<ask(y)-ask(x-1)<<endl;
        }
        if (ch=='C')
        {
            ll x,y,d;
            scanf("%lld%lld%lld\n",&x,&y,&d);
            add(x,d);
            add(y+1,-d);
        }
    }
    return 0;
}

感谢lcf大佬的博客
感谢lyd大佬的蓝书