树状数组 1

链接

纯粹的模板题,完全套公式就行了啦

#include<iostream>
#include<vector>

typedef long long ll;
using namespace std;
vector<ll>num;
int n, m;
int lowbit(int x) {
	return x & -x;
}

ll query(int l, int r) {
	ll sum_r = 0, sum_l = 0;
	for (;r;r-=lowbit(r)) {
		sum_r += num[r];
	}
	l -= 1;
	for (;l;l -= lowbit(l)) {
		sum_l += num[l];
	}
	return sum_r - sum_l;
}

void update(int idx, ll value) {
	for (;idx <= n;idx += lowbit(idx)) {
		num[idx] += value;
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m;
	num.resize(n + 1);
	for (int i = 1;i <= n;i++) {
		cin >> num[i];
	}
	int k = 1;
	while (2 * k <= n) {
		for (int i = 2 * k;i <= n;i += 2 * k) {
			num[i] += num[i - k];
		}
		k *= 2;
	}
	for (int i = 0;i < m;i++) {
		int number, x, k;
		cin >> number >> x >> k;
		if (number == 1) {
			update(x, k);
		}
		else if (number == 2) {
			cout << query(x, k) << '\n';
		}
	}
}

时间复杂度:O(n+mlog n)

空间复杂度:O(n)