tr1 b1
tr2 b1 b2
tr3 b1 b2 b3
tr4 b1 b2 b3 b4
. .
. .
. .
trn b1 b2 b3 b4 ..... bn

所以为了求tr的前缀和，可以将这个矩阵的上半部分用b1~bn补起来
然后再减去b1 * 1 + b2 * 2 + … + bn * n,即可求得区间和

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;

const int N = 100010;

LL a[N], tr1[N], tr2[N]; // tr1[]维护差分数组的值，tr2[]维护i*b[i]的值
LL n, m;

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

void add(LL tr[], LL x, LL k)
{
    for (int i = x; i <= n; i += lowbit(i))
        tr[i] += k;
}

LL sum(LL tr[], LL x)
{
    LL res = 0;
    for (int i = x; i; i -= lowbit(i))
        res += tr[i];
    return res;
}

LL SUM(LL x)
{
    return sum(tr1, x) * (x + 1) - sum(tr2, x); // 区间查询就变成了由x + 1个差分矩阵的和减去上面的三角形，也就是tr2[]维护的值
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m;

    for (int i = 1; i <= n; i ++) cin >> a[i];

    for (int i = 1; i <= n; i ++)
    {
        LL y = a[i] - a[i - 1];
        add(tr1, i, y);
        add(tr2, i, i * y);
    }

    while(m --)
    {
        char ch;
        cin >> ch;
        if (ch == 'Q')
        {
            LL l, r;
            cin >> l >> r;
            cout << SUM(r) - SUM(l - 1) << endl;
        }
        else
        {
            int l, r, d;
            cin >> l >> r >> d;
            add(tr1, l, d), add(tr2, l, l * d);
            add(tr1, r + 1, -d), add(tr2, r + 1, (r + 1) * -d);
        }
    }

    return 0;
}