树状数组（c++版）

树状数组模板（具体原理及说明见文末）

void update(vector& a, int pos, int k) { //更新数组
	while (pos <= n) {
		a[pos] += k;
		pos += lowbit(pos);
	}
}

int getsum(vector &a, int pos) { // 得到从1加到pos的和
	int ans = 0;
	while (pos > 0) {
		ans += a[pos];
		pos -= lowbit(pos);
	}
	return ans;
}

例题：洛谷p3373

#include

#include

using namespace std;
typedef long long ll;

ll n, m;

inline ll lowbit(ll x) {
	return x&(-x);
}

inline void update(vector& a, ll pos, ll k) {
	while (pos <= n) {
		a[pos] += k;
		pos += lowbit(pos);
	}
}

inline ll getsum(vector &a, ll pos) {
	ll ans = 0;
	while (pos > 0) {
		ans += a[pos];
		pos -= lowbit(pos);
	}
	return ans;
}

int main() {
	cin.sync_with_stdio(0);
	
	cin >> n >> m;
	vector a(n+1);
	vector tr1(n + 2), tr2(n + 2);
	for (ll i = 1; i <= n; i++) {
		cin >> a[i];
		update(tr1, i, a[i] - a[i - 1]);
		update(tr2, i, (a[i] - a[i - 1]) * (i - 1));
		
	}
	for (ll i = 0; i < m; i++) {
		ll op;
		cin >> op;
		if (op == 1) {
			ll x, y, k;
			cin >> x >> y >> k;
			update(tr1, x, k);
			update(tr1, y+1, -k);
		
			update(tr2, x, k*(x-1));
			update(tr2, y + 1, -k*y);
		}
		else {
			ll x, y;
			cin >> x >> y;
			ll ans = 0;
			
			cout << y * getsum(tr1,y) - getsum(tr2,y) - ((x - 1) * getsum(tr1, x - 1 ) - getsum(tr2, x - 1)) << endl;
		
		}
	}
}

参考了一下两篇文章，原理讲得很详细，我这里只是在将其转换为了c++代码。
洛谷p3372
cnblogs