题目描述

如题，已知一个数列，你需要进行下面两种操作：

• 将某一个数加上 $x$
• 求出某区间每一个数的和

输入格式

第一行包含两个正整数 $n,m$，分别表示该数列数字的个数和操作的总个数。

第二行包含 $n$ 个用空格分隔的整数，其中第 $i$ 个数字表示数列第 $i$ 项的初始值。

接下来 $m$ 行每行包含 $3$ 个整数，表示一个操作，具体如下：

• 1 x k 含义：将第 $x$ 个数加上 $k$
• 2 x y 含义：输出区间 $[x,y]$ 内每个数的和

输出格式

输出包含若干行整数，即为所有操作 $2$ 的结果。

样例 #1

样例输入 #1

5 5
1 5 4 2 3
1 1 3
2 2 5
1 3 -1
1 4 2
2 1 4

样例输出 #1

14
16

提示

【数据范围】

对于 $30\%$ 的数据，$1 \le n \le 8$，$1\le m \le 10$；
对于 $70\%$ 的数据，$1\le n,m \le 10^4$；
对于 $100\%$ 的数据，$1\le n,m \le 5\times 10^5$。

数据保证对于任意时刻，$a$ 的任意子区间（包括长度为 $1$ 和 $n$ 的子区间）和均在 $[-2^{31}, 2^{31})$ 范围内。

样例说明：

故输出结果14、16

---

#include <iostream>
#include <vector>

using namespace std;

int lowbit(int x) {
	// x 的二进制中，最低位的 1 以及后面所有 0 组成的数。
	// lowbit(0b01011000) == 0b00001000
	//          ~~~~^~~~
	// lowbit(0b01110010) == 0b00000010
	//          ~~~~~~^~
	return x & -x;
}

//维护运算为加法的树状数组，即区间求和，单点加数 
struct FenwickTree {
	vector<int> c;
	
	//a数组的元素应该从a[1]开始 
	explicit FenwickTree(vector<int> a) : c(a.size(), 0) {
		// Θ(n) 建树
		for (int i = 1; i < a.size(); ++i) {
	    	c[i] += a[i];
	    	int j = i + lowbit(i);
	    	if (j < a.size()) c[j] += c[i];
	  	}
	}
	
	// a[1]..a[x]的和
	int query(int x) {  
		int ans = 0;
		while (x > 0) {
			ans = ans + c[x];
			x = x - lowbit(x);
		}
		return ans;
	}
	
	//令a[x] += k 
	void modify(int x, int k) {
		while (x < c.size()) {  // 不能越界
			c[x] = c[x] + k;
			x = x + lowbit(x);
		}
	}
	
};

int main() {
	ios::sync_with_stdio(false);
	int n,m;
	cin >> n >> m;
	vector<int> a = vector<int>(n + 1);
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	} 
	FenwickTree ft = FenwickTree(a);
	for (int i = 0; i < m; i++) {
		int op;
		cin >> op;
		if (op == 1) {
			int x, k;
			cin >> x >> k;
			ft.modify(x, k);
		} else {
			int x, y;
			cin >> x >> y;
			cout << (ft.query(y) - ft.query(x - 1)) << endl;
		}
	}
	return 0;
}

单点修改和区间查询的时间复杂度均是O(log n)

参考：

https://oi.wiki/ds/fenwick/

https://www.luogu.com.cn/problem/P3374