一个简单的整数问题

树状数组 差分 区间修改 单点查询 242. 一个简单的整数问题 - AcWing题库

给定长度为 $N$ 的数列 $A$，然后输入 $M$ 行操作指令。

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

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

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

输入格式

第一行包含两个整数 $N$ 和 $M$。

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

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

输出格式

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

每个答案占一行。

数据范围

$1\le N,M\le 10^5$,
$|d|\le 10000$,
$|A[i]|\le 10^9$

输入样例：

10 5
1 2 3 4 5 6 7 8 9 10
Q 4
Q 1
Q 2
C 1 6 3
Q 2

输出样例：

4
1
2
5

思路

区间修改, 单点查询。

普通的树状数组可以实现单点修改区间查询, 这里需要做一下转化。因为树状数组最后求的是前缀和。 可以先把原数组初始化为差分数组, $add(i,a[i]-a[i-1])$ 即可。

然后求单点的话就是 $sum(i)$。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
const int N = 1e5 + 10;
typedef long long LL;
LL t[N];
int n,m;
 
int lowbit(int x)
{
    return x & -x;
}
 
void add(int u, int x)
{
    for(int i = u; i <= n; i+= lowbit(i)) t[i] += x;
}
 
LL sum(int x)
{
    LL res = 0;
    for(int i = x; i; i -= lowbit(i)) res += t[i];
    return res;
}
 
int main()
{
    cin >> n >> m;
    int prev = 0;
    for(int i = 1; i <= n; i++)
    {
        int t;
        cin >> t;
        add(i, t - prev);
        prev = t;
    }
    
    while(m--)
    {
        char s[2];
        int l,r,d;
        cin >> s >> l;
        if(s[0] == 'Q')
            cout << sum(l)<< endl;
        else {
            cin >> r >> d;
            add(l, d);
            add(r + 1, -d);
        }
    }
    return 0;
}