线段树

一维线段树

Xenny

树状数组

一维树状数组

嗯嗯还是Xenny

胡小兔

区修单差·差分

说一下差分。这个东西一直没搞明白，后来也没再想。

对于树状数组维护区间更改、单点查询而言，差分是很好的一个方法。

设当前要使区间 \([l, r]\) 的数值加上 \(x\)，那么就使\(l\)位置的数值+=x，在 \(r+1\) 位置的数值-=x。查询的时候只需要查询当前点的前缀和。

考虑为什么这样更新。

如果使区间 \([l, r]\) 的数值加上 \(x\)，那么 \(l\) 与 \(l-1\) 的差值就会增加了 \(x\)，而 \(r+1\) 与 \(r\) 的差值就会减少 \(x\)。故。

用代码写出来就是这样：

inline void Update(int k, int w){
	while (k <= n)
		C[w] += k, k += lowbit(k);
}
inline void Range_Update(int l, int r, int w){
	Update(l, w), Update(r+1, -w);
}
inline int Query(int k){
	int res(0);
	while (k != 0)
		res += C[k], k -= lowbit(k);
	return res;
}

区修区查

区修区查你闲的没事用树状数组干嘛。自己去写个线段树不就行了。(doge

二维树状数组