差分

发表于 分类于 ， 阅读次数： 本文字数： 332 阅读时长 ≈ 1 分钟 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
struct LazySum {
	vector<int> ps;
	LazySum(int n) : ps(n, 0) {}

	//[l, r]
	void add(int l, int r, int val) {
		if (l > r) return;
		ps[l] += val;
		ps[r + 1] -= val;
	}
	void pushToAndClear(vector<int> &d) {
		int sum = 0;
		fore (i, 0, sz(ps)) {
			sum += ps[i];
			ps[i] = 0;
			if (i < sz(d))
				d[i] += sum;
		}
	}
};