【题目来源】
洛谷：P3374 【模板】树状数组 1 - 洛谷
【题目描述】
如题，已知一个数列，你需要进行下面两种操作：
- 将某一个数加上 x
- 求出某区间每一个数的和
【输入】
第一行包含两个正整数 n,m，分别表示该数列数字的个数和操作的总个数。
第二行包含 n 个用空格分隔的整数，其中第 i 个数字表示数列第 i 项的初始值。
接下来 m 行每行包含 3 个整数，表示一个操作，具体如下：
1 x k含义：将第 x 个数加上 k2 x y含义：输出区间 [x,y] 内每个数的和
【输出】
输出包含若干行整数，即为所有操作 2 的结果。
【输入样例】
5 5
1 5 4 2 3
1 1 3
2 2 5
1 3 -1
1 4 2
2 1 4
【输出样例】
14
16
【算法标签】
《洛谷 P3374 树状数组1》 #树状数组#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 500005; // 定义数组最大长度int n, m; // n-数组长度，m-操作次数
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; // op-操作类型，x和y-操作参数// 初始化树状数组for (int i = 1; i <= n; i++){cin >> y;change(i, y); // 将初始值插入树状数组}// 处理每个操作for (int i = 1; i <= m; i++){cin >> op >> x >> y;// 操作1：单点修改if (op == 1){change(x, y);}// 操作2：区间查询else{// 输出区间[x,y]的和cout << query(y) - query(x - 1) << endl;}}return 0;
}
#include <bits/stdc++.h>
using namespace std;const int N = 500005; // 定义数组最大长度int n, m; // n-数组长度，m-操作次数
int tr[N]; // 树状数组（Binary Indexed Tree）// 计算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; // op-操作类型，x和y-操作参数// 初始化树状数组for (int i = 1; i <= n; i++){cin >> y;add(i, y); // 将初始值插入树状数组}// 处理每个操作for (int i = 1; i <= m; i++){cin >> op >> x >> y;// 操作1：单点修改，在位置x增加yif (op == 1){add(x, y);}// 操作2：区间查询，输出区间[x,y]的和else{// 利用前缀和计算区间和：sum[y] - sum[x-1]cout << query(y) - query(x - 1) << endl;}}return 0;
}
【运行结果】
5 5
1 5 4 2 3
1 1 3
2 2 5
14
1 3 -1
1 4 2
2 1 4
16