1264. 动态求连续区间和-acwing -树状数组

原题链接：1264. 动态求连续区间和 - AcWing题库

给定 n 个数组成的一个数列，规定有两种操作，一是修改某个元素，二是求子数列 [a,b] 的连续和。

输入格式

第一行包含两个整数 n 和m，分别表示数的个数和操作次数。

第二行包含 n 个整数，表示完整数列。

接下来 m 行，每行包含三个整数 k,a,b （k=0，表示求子数列[a,b]的和；k=1，表示第 a 个数加 b）。

数列从 1 开始计数。

输出格式

输出若干行数字，表示 k=0 时，对应的子数列 [a,b]的连续和。

数据范围

1≤n≤100000,
1≤m≤100000，
1≤a≤b≤n,
数据保证在任何时候，数列中所有元素之和均在 int 范围内。

输入样例：

10 5
1 2 3 4 5 6 7 8 9 10
1 1 5
0 1 3
0 4 8
1 7 5
0 4 8

输出样例：

11
30
35

 

#include <iostream>
using namespace std;// 定义常量 N，表示树状数组的最大长度
const int N = 100000 + 1000;// 全局变量
int n, m;       // n 表示数组长度，m 表示操作次数
int tr[N];      // 树状数组，用于维护前缀和// 计算 x 的最低位 1 的值
int lowbit(int x)
{return x & -x;
}// 查询树状数组中 [1, x] 的前缀和
int query(int x)
{int res = 0; // 初始化结果为 0for (int i = x; i > 0; i -= lowbit(i)) // 从 x 开始，逐步减去最低位{res += tr[i]; // 累加树状数组中的值}return res; // 返回前缀和
}// 在树状数组中增加值 v
void add(int x, int v, int n)
{for (int i = x; i <= n; i += lowbit(i)) // 从 x 开始，逐步增加最低位{tr[i] += v; // 更新树状数组中的值}
}int main()
{// 输入数组长度 n 和操作次数 mcin >> n >> m;// 初始化树状数组，读取数组元素并构建树状数组for (int i = 1; i <= n; i++){int a;cin >> a; // 输入数组的第 i 个元素add(i, a, n); // 将第 i 个元素加入树状数组}// 处理 m 次操作for (int i = 1; i <= m; i++){int k, a, b;cin >> k >> a >> b; // 输入操作类型 k 和参数 a, bif (k == 0) // 查询操作{// 查询区间 [a, b] 的和int resb = query(b);     // 查询 [1, b] 的前缀和int resa = query(a - 1); // 查询 [1, a-1] 的前缀和cout << resb - resa << endl; // 输出区间 [a, b] 的和}else // 更新操作{// 将第 a 个位置的值增加 badd(a, b, n);}}return 0;
}