题目链接：POJ3468

题目大意：给你一段长度为n得数字序列，并且有q次操作，这些操作可能是查询[l,r]的数字和或者是修改[l,r]之间的数字。每次做出相应操作，查询则输出结果。

解题思路：关于数字序列区间问题，可以用线段树，但要加个延迟标记(之后更新这种做法)。这里通过树状数组的性质，并且预处理树状数组(差分操作)，使其能够区间更新。

关于区间修改的树状数组

  • 这里树状数组我们用c[maxn]表示，数组序列我们用val[maxn]表示。
  • 差分操作：我们设数组tp[i] = val[i] - val[i - 1] (i >= 1, val[0] = 0)
  • 于是有：val[i] = tp[i] + val[i - 1]
  • 迭代一下：val[i - 1] = tp[i - 1] + val[i - 2]
  • 则:val[i] = tp[i] + tp[i - 1] + val[i - 2] = tp[i] + tp[i - 1] + … + tp[1]
  • 上面那个还有最后一项val[0] = 0省略
  • 于是，利用c数组维护tp的前缀和可以用getsum来求得val。
  • 那么，如果是解决区间修改单点查询的问题时，我们到此就完成了。修改操作：update(left, num); update(right, num); 查询操作：getsum(i);
  • 这里不难发现，如果是区间查询时，比如查询[3,6]：其实就是getsum(3) + getsum(4) + getsum(5) + getsum(6)。但如果数据规模一大，每次查询的时候都要做到接近O(n)的加法，体现不了树状数组的优势。观察一下，这个[3,6]的查询操作每次getsum(k)做的是从tp[1]加到tp[k]的和，如果我们定义一个getsum2(k)：(tp[1]) + (tp[1] + tp[2]) + (tp[1] + tp[2] + tp[3]) + (tp[1] + … + tp[k])表示从getsum(1) + …getsum (k)的前缀和。式子变形一下：(tp[1] + tp[2] + … + tp[k]) * k - (tp[1] * 0 + tp[2] * 1 + tp[3] * 2 + … + tp[k] * (k - 1) )。 这样一来，[3,6]区间的和就可以通过getsum2(6) - getsum2(3 - 1)求得！但这个形式可能不好处理，我们通过变形式子: k * getsum(k,0) - getsum(k,1)来求得，其中0表示计算tp的前缀和，1表示tp[k] * (k - 1)的前缀和，于是，我们要有两个树状数组！注意可能爆整型！

AC代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <string>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <vector>
#include <utility>

using namespace std;
const int maxn = (int)1e5+5;
typedef long long LL;

LL c[2][maxn];
int n;

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

void add (int idx, LL num, int select) {
	while (idx <= n) {
		c[select][idx] += num;
		idx += lowbit(idx);
	}
}

LL get_sum (int idx, int select) {
	LL ans = 0;
	while (idx > 0) {
		ans += c[select][idx];
		idx -= lowbit(idx);
	}
	return ans;
}

LL query (int s) {  //1-s:区间和
	return s * get_sum(s, 0) - get_sum(s, 1);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);	cout.tie(0);
	LL q,tmp,i,j,k,before;
	string command;
	while (cin >> n >> q) {
		memset(c[0], 0, sizeof(c[0]));
		memset(c[1], 0, sizeof(c[1]));
		before = 0;
		for (i = 1; i <= n; i++) {
			cin >> tmp;
			add(i, tmp - before, 0);
			add(i, (i - 1) * (tmp - before), 1);
			before = tmp;
		}
		while (q--) {
			cin >> command;
			if (command.at(0) == 'Q') {
				cin >> i >> j;
				cout << (query(j) -query(i - 1)) << '\n';
			}else {
				cin >> i >> j >> k;
				add(i, k, 0);
				add(j + 1, -k, 0);
				add(i, (i - 1) * k, 1);
				add(j + 1, j * (-k), 1);
			}
		}
	}
	return 0;
}