蓝桥杯康复训练 Day4 （前缀和）（树状数组）（线段树）_前缀和+线段树

昨天没状态摆了一天，今天复习一下各种区间问题

---

前缀和

常规遍历

区间求和复杂度 O(n)
单点修改复杂度 O(1)

前缀和

区间求和复杂度 O(1)
单点修改复杂度 O(n)

前缀和数组中每个值覆盖的是从开始到该点整个区间的和值
求 i ~ j 的区间和值可以通过 s [ j ] - s [ i - 1 ] 计算

可以扩展成二维三维的前缀和
在单点修改时需要对所有覆盖该点的值进行修改

在对区间求和复杂度要求高时使用

蓝桥杯–前缀和1

---

树状数组

对比前缀和复杂度

前缀和

区间求和复杂度 O(1)
单点修改复杂度 O(n)

树状数组

区间求和复杂度 O(logn)
单点修改复杂度 O(logn)

蓝桥杯–树状数组1

常用于综合考虑区间求和和单点修改的复杂度

与前缀和数组不同在于，树状数组的每个点覆盖的区间值是由它的下标决定的，如

tr [ 8 ] 覆盖前8个值的和，即 w [ 1 ] ~ w [ 8 ]
tr [ 9 ] 覆盖前1个值的和，即 w [ 9 ] ~ w [ 9 ]
tr [ 10 ] 覆盖前2个值的和，即 w [ 9 ] ~ w [ 10 ]
tr [ 11 ] 覆盖前1个值的和，即 w [ 11 ] ~ w [ 11 ]
tr [ 12 ] 覆盖前4个值的和，即 w [ 9 ] ~ w [ 12 ]

覆盖长度可以通过对下标的计算得来，定义这个计算操作lowbit

	static int lowbit(int x) {
		return x & -x;
	}
1
2
3

计算涉及到二进制知识不详述，总结就是 x 可以被一个最大的 2^k 整除，那么 x 即可覆盖 2^k 个值，lowbit返回值即是这个 2^k

如 lowbit(12) = 2² = 4，因此 tr [ 12 ] 覆盖 w [ 9 ] ~ w [ 12 ] 共4个值的和，即

tr[ x ] = ( w [ x - lowbit( x ) ]，w [ x ] ]
（左端点不覆盖，因此左开右闭，该左端点即是左边下一个区间的右端点）

由此可以得出计算前缀和的方法query，每次使用lowbit得到左侧下一区间的右端点，递推直到最左端

可以通过两前缀和相减来实现区间求和

	static int query(int x) {
		int res = 0;
		for (int i = x; i >= 1; i -= lowbit(i)) {
			res += tr[i];
		}
		return res;
	}
1
2
3
4
5
6
7

同理也可以得出单点修改的方法modify，由于覆盖该点区间在右侧，并且右侧下一区间的 tr 坐标即是该坐标加上lowbit，因此可以使用lowbit向右递推直到最右端

树状数组的初始化也可以通过该函数实现

	static void modify(int x, int v) {
		for (int i = x; i <= n; i += lowbit(i)) {
			tr[i] += v;
		}
	}
1
2
3
4
5

有些时候只要求区间求和用前缀和就好，没必要树状数组很麻烦
（比如去年国赛