【题目来源】
洛谷：P3368 【模板】树状数组 2 - 洛谷
【题目描述】
如题，已知一个数列，你需要进行下面两种操作：
- 将某区间每一个数加上 \(x\)；
- 求出某一个数的值。
【输入】
第一行包含两个整数 \(N\)、\(M\)，分别表示该数列数字的个数和操作的总个数。
第二行包含 \(N\) 个用空格分隔的整数，其中第 \(i\) 个数字表示数列第 \(i\) 项的初始值。
接下来 \(M\) 行每行包含 \(2\) 或 \(4\)个整数，表示一个操作，具体如下：
操作 \(1\)格式：1 x y k 含义：将区间 \([x,y]\) 内每个数加上 \(k\)；
操作 \(2\)格式：2 x 含义：输出第 \(x\) 个数的值。
【输出】
输出包含若干行整数，即为所有操作 \(2\) 的结果。
【输入样例】
5 5
1 5 4 2 3
1 2 4 2
2 3
1 1 5 -1
1 3 5 7
2 4
【输出样例】
6
10
【算法标签】
《洛谷 P3368 树状数组2》 #树状数组#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 500005; // 定义数组最大长度int n, m; // n-数组长度，m-操作次数
int a[N]; // 原始数组
int s[N]; // 树状数组（用于维护差分数组）// 计算x的最低有效位（用于树状数组索引计算）
int lowbit(int x)
{return x & -x;
}// 更新树状数组：在位置x增加k
void change(int x, int k)
{// 向上更新所有相关节点while (x <= n){s[x] += k;x += lowbit(x);}
}// 查询前缀和：计算前x个元素的和
int query(int x)
{int t = 0;// 向下累加所有相关节点while (x){t += s[x];x -= lowbit(x);}return t;
}int main()
{// 输入数组长度n和操作次数mcin >> n >> m;int op, x, y, k; // op-操作类型，x/y/k-操作参数// 输入原始数组for (int i = 1; i <= n; i++){cin >> a[i];}// 处理每个操作for (int i = 1; i <= m; i++){cin >> op >> x;// 操作1：区间修改，对区间[x,y]每个元素增加kif (op == 1){cin >> y >> k;// 差分操作：在x处+k，在y+1处-kchange(x, k);change(y + 1, -k);}// 操作2：单点查询，输出a[x]加上差分数组的前缀和else{cout << a[x] + query(x) << endl;}}return 0;
}
// 使用acwing模板二刷
#include <bits/stdc++.h>
using namespace std;const int N = 500005; // 定义数组最大长度int n, m; // n-数组长度，m-操作次数
int a[N]; // 原始数组
int tr[N]; // 树状数组（用于维护差分数组）// 计算x的最低有效位（用于树状数组索引计算）
int lowbit(int x)
{return x & -x;
}// 向树状数组添加值：在位置x增加c
void add(int x, int c)
{// 从x开始向上更新所有相关节点for (int i = x; i <= n; i += lowbit(i)){tr[i] += c;}
}// 查询前缀和：计算前x个元素的和
int query(int x)
{int res = 0;// 从x开始向下累加所有相关节点for (int i = x; i; i -= lowbit(i)){res += tr[i];}return res;
}int main()
{// 输入数组长度n和操作次数mcin >> n >> m;int op, x, y, k; // op-操作类型，x/y/k-操作参数// 输入原始数组for (int i = 1; i <= n; i++){cin >> a[i];}// 处理每个操作for (int i = 1; i <= m; i++){cin >> op >> x;// 操作1：区间修改，对区间[x,y]每个元素增加kif (op == 1){cin >> y >> k;// 差分操作：在x处+k，在y+1处-kadd(x, k);add(y + 1, -k);}// 操作2：单点查询，输出a[x]加上差分数组的前缀和else{cout << a[x] + query(x) << endl;}}return 0;
}
【运行结果】
5 5
1 5 4 2 3
1 2 4 2
2 3
6
1 1 5 -1
1 3 5 7
2 4
10