AcWing 242. 一个简单的整数问题

题目传送门

算法分析
树状数组（变型类型：差分）

树状数组主要解决的是

1、a[x] += c (单点修改)
2、求a[L ~ R] (前缀和)

总结：单点加，区间求和

本题要求求的是

1、a[L ~ R] += c
2、求a[x]
因为 前缀和 和 差分 是一种逆运算，因此本题将原数组a[]转换 差分数组b[]，就变成了树状数组的模型

1、a[L ~ R] += c 等价于 b[L] += c，b[R + 1] -= c
2、求a[x] 等价于 求b[1 ~ x]的前缀和

总结：区间加，单点求和

注意：在求前缀和时，要特别注意数据范围，防止爆\(int\)

#include 

using namespace std;
typedef long long LL;
const int N = 100010;

int n, m;
int a[N];

//注意下这里与标准模板的不同，因为求和可能会超过int上限，需要开long long
// t[i]表示树状数组i结点覆盖的范围和
LL t[N];

//返回非负整数x在二进制表示下最低位1及其后面的0构成的数值
int lowbit(int x) {
    return x & -x;
}
//将序列中第x个数加上k
void add(int x, int k) {
    for (int i = x; i <= n; i += lowbit(i)) t[i] += k;
}
//查询序列前x个数的和
LL sum(int x) {
    int sum = 0;
    for (int i = x; i; i -= lowbit(i)) sum += t[i];
    return sum;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    //树状数组初始化，保存差分值
    for (int i = 1; i <= n; i++) add(i, a[i] - a[i - 1]);
    while (m--) {
        char op;
        int l, r, d;
        cin >> op >> l;
        if (op == 'C') { //修改
            cin >> r >> d;
            //差分，在l处加上d,在r+1位置减去d
            add(l, d), add(r + 1, -d);
        } else
            printf("%lld\n", sum(l)); //求前缀和
    }
    return 0;
}