树状数组 2

链接

这个模板题有点特殊,似乎和树状数组反过来了

我们可以将这个转换为差分数组

如1 5 5 3 4变为 1 4 0 -2 1,这样我们修改某个区间的值的时候之后这个区间的头部和尾部的后一个数发上了变化(总感觉在哪儿做过类似的题)

#include<iostream>
#include<vector>
using namespace std;
vector<int>num;
int n, m;

int lowbit(int x) {
	return x & -x;
}

long long query(int x) {
	long long sum = 0;
	for (;x;x -= lowbit(x)) {
		sum += num[x];
	}
	return sum;
}

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m;
	num.resize(n + 1, 0);
	vector<int>a(n + 1, 0);
	for (int i = 1;i <= n;i++) {
		cin >> a[i];
	}
	for (int i = n;i > 0;i--) {
		a[i] = a[i] - a[i - 1];
	}
	for (int i = 1;i <= n;i++) {
		update(i, a[i]);
	}
	while (m--) {
		int q, b, c, d;
		cin >> q;
		if (q == 1) {
			cin >> b >> c >> d;
			update(b, d);
			if(c<n)	update(c+1, -d);
		}
		else {
			cin >> b;
			cout << query(b) << '\n';
		}
	}
}

时间复杂度:O(n +m log n)

空间复杂度:O(n)