AcWing 243. 一个简单的整数问题2

题目传送门

一、题目总结

树状数组可以解决：

区间修改，区间查询 本题

如果是区间修改，单点查询。只需用树状数组维护一个差分数组\(b\)。假设查询位置\(x\)，那么\(\displaystyle \sum_{i=1}^{x}b_i\)就是\(x\)位置上的变化量。

考虑引入区间查询。首先最暴力想，假设查询\([1,r]\)。那么\([1,r]\)的答案=\(\displaystyle \sum_{i=1}^{r}\sum_{j=1}^{i}b_j\)
不妨举个特例，更直观些。假设查询\([1, 4]\)。那么\(ans=(b_1)+(b_1+b_2)+(b_1+b_2+b_3)+(b_1+b_2+b_3+b_4)=4b_1+3b_2+2b_3+1b_4\)。

换成查询\([1, r]\)。那么\(\displaystyle ans=(r+1-1)b_1+(r+1-2)b_2+(r+1-3)b_3+…+(r+1-r)b_r = (r+1)\sum_{i=1}^{r}b_i-\sum_{i=1}^{r}i*b_i\)

显然第一项用树状数组\(tr1\)维护\(b\)数组可求出。第二项求不出。但令\(c=i*b[i]\)，新开一个树状数组\(tr2\)维护\(c\)就行了。

二、实现代码

#include 
using namespace std;
typedef long long LL;
const int N = 100010;
//据说还可以用线段树和分块来做，我不会，慢慢来吧
int n, m;
int a[N];

//处理多套树状数组的模板代码
LL tr1[N]; // 维护b[i]的前缀和
LL tr2[N]; // 维护c=b[i]*i的前缀和
int lowbit(int x) {
    return x & -x;
}
void add(LL tr[], int x, LL c) {
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}
LL sum(LL tr[], int x) {
    LL res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

//本题的扩展函数
LL prefix_sum(int x) { //利用数学推导出的公式计算
    return sum(tr1, x) * (x + 1) - sum(tr2, x);
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i]; //原数组
    for (int i = 1; i <= n; i++) {
        int b = a[i] - a[i - 1]; //原数组的差分值
        //利用树状数组tr1记录位置i处有数字b
        //利用树状数组tr2记录位置i处有数字b*i
        add(tr1, i, b), add(tr2, i, (LL)b * i);
    }

    while (m--) {
        char op;
        int l, r, d;
        cin >> op >> l >> r;
        if (op == 'Q') {
            printf("%lld\n", prefix_sum(r) - prefix_sum(l - 1));
        } else {
            cin >> d;                            //更新
            add(tr1, l, d), add(tr1, r + 1, -d); //正常差分
            /*
            在理解tr1的基础上推tr2：因为维护tr1只需要修改值b[l] 和 b[r+1]， 而tr2的定义为ib[i]
            所以这次改动的tr2的影响也只有lb[l] 和(r+1) * b[r+1] ，并且值为系数(l or r+1) * (b[l or r+1]
            增加的值）
            */
            add(tr2, l, l * d), add(tr2, r + 1, (r + 1) * -d);
        }
    }
    return 0;
}