python/TangDou/AcWing/BIT/242.md

##[$AcWing$ $242$. 一个简单的整数问题](https://www.acwing.com/problem/content/248/)

### 一、题目描述
给定长度为 $N$ 的数列 $A$，然后输入 $M$ 行操作指令。

第一类指令形如 `C l r d`，表示把数列中第 $l∼r$ 个数都加 $d$。

第二类指令形如 `Q x`，表示询问数列中第 $x$ 个数的值。

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

**输入格式**
第一行包含两个整数 $N$ 和 $M$。

第二行包含 $N$ 个整数 $A[i]$。

接下来 $M$ 行表示 $M$ 条指令，每条指令的格式如题目描述所示。

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

每个答案占一行。

### 二、算法分析

#### 树状数组 + 差分

树状数组主要解决的是

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

**总结：单点加，区间求和**

本题要求求的是

1、`a[L ~ R] += c`
2、求`a[x]`

因为 **前缀和** 和 **差分** 是一种逆运算，因此本题将原数组`a[]` 转换 **差分数组**`b[]`，就变成了树状数组的模型

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

**总结：区间加，单点求和**

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

### 三、实现代码

```cpp {.line-numbers}
#include <bits/stdc++.h>

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

int n, m;
int a[N];

// 树状数组模板
int tr[N];

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

void add(int x, int c) {
    for (int i = x; i < N; i += lowbit(i)) tr[i] += c;
}

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

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

    // 方法1：也可以这么做，但是方法比较笨拙
    // 树状数组初始化，保存差分值
    // for (int i = 1; i <= n; i++) add(i, a[i] - a[i - 1]);

    while (m--) {
        char op[2];
        scanf("%s", op);

        if (op[0] == 'C') { // 修改
            int l, r, d;
            scanf("%d %d %d", &l, &r, &d);
            // 差分，在l处加上d,在r+1位置减去d
            add(l, d), add(r + 1, -d);
        } else {
            int l;
            scanf("%d", &l);
            // 方法1
            // printf("%lld\n", sum(l)); // 求前缀和
            // 推荐方法
            printf("%lld\n", a[l] + sum(l)); // 求前缀和
        }
    }
    return 0;
}
```