现在已经知道：树状数组可以用于

1.某个点 修改

2.求某段区间的和

或

1.某个区间修改

2.求某个点的和

现在，再次进行拓展，

1.某个区间进行修改

2.求某个区间的和

首先对于操作1，我们依然使用差分数组来进行修改某个区间的值。和上面一题一样。

而求某个区间的和呢？ a[1] + a[2] + a[3] + a[4].....

a[1] = b[1],

a[2] = b[1] + a[2]

a[3] = b[1] + b[2] + b[3],  .....

那么应该如何求区间的和呢？

首先我们想到求某个区间的和，要快速求的话，肯定需要前缀和的思想。

那么，这里有一个技巧，

 

 填充上红色部分后，就可以使用一个技巧，按照列的形式

黑色部分的值，也就是我们要求的a[1~n]的前缀和:

(b1 + b2 + b3 + .... + bn) * (n + 1) - 1 * b1 - 2 * b2 - 3 * b3 - ......-n * bn

== (b1 + b2 + b3 + .... + bn) * (n + 1) - (1 * b1 + 2 * b2 + 3 * b3 + ... + n * bn);

前面的为b[]的1~n的前缀和。

后面的为 i * b[i] 的 1~n的前缀和。

题目链接：https://www.acwing.com/problem/content/244/

题目：

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

输出格式

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

每个答案占一行。

数据范围

1≤N,M≤1e5,
|d|≤10000,
|A[i]|≤1e9

输入样例：

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

代码实现：

# include <iostream>
using namespace std;

const int N = 1e5 + 10;

int a[N];
int b[N];
long long c1[N];
long long c2[N];

int n,m;

int lowbit(int x)
{
    return x & -x;
}

void add(long long * c , int i , long long v)
{
    for(int j = i ; j <= n ; j+= lowbit(j) )
    {
        c[j] += v;
    }
}

long long sum(long long * c , int i)
{
    long long res  = 0;
    for(int j = i ; j ; j -= lowbit(j))
    {
        res += c[j];
    }
    return res;
}

long long get_sum(int x)
{
    return sum(c1,x) * (x + 1) - sum(c2,x);
}

int main()
{
    scanf("%d %d",&n,&m);
    for(int i = 1 ; i <= n ; i++)
    {
        scanf("%d",&a[i]);
    }
    
    
    for(int i = 1 ; i <= n ; i++)
    {
        b[i] = a[i] - a[i - 1];
    }
    
    
    for(int i = 1 ; i <= n ; i++)  // 给c1[],c2[]赋初值
    {
        add(c1,i,b[i]);
        add(c2,i,(long long)i*b[i]); // b[i] 为 a[i] - a[i - 1],可能为1e9 , 而i可能为1e5
    }
    
    
    while(m--)
    {
        string ch;
        int l,r;
        cin >> ch >> l >> r;
        if(ch == "Q")
        {
            printf("%lld\n",get_sum(r) - get_sum(l - 1));
        }
        else
        {
            int d;
            scanf("%d",&d);
            add(c1,l,d);
            add(c1,r + 1,-d);
            
            add(c2,l,l * d);
            add(c2,r + 1,(r + 1) * (-d));
        }
    }
    return 0;
}