倍增原理

你可以选取任意个数, 放到一个集合, 即该集合为S
随机给定一个>= 0 且 <= N的 整数x
你的集合S 需要选出一些元素(集合内每个元素只能使用1次), 使得 这些元素之和为x
… 如何选取S集合, 才能使得 集合的大小 最小.

选取: $2^0,2^1,2^2,2^3,...,2^n且2^n为最大的\le N的幂$ 作为集合S
(1, 该集合, 可以凑出任意的 [0, n]范围的数)
(2, 平均下来, 最多需要logN个元素, 便可以 凑成一个数)

也就是, 对于一个数, 进行二进制拆分, 比如n = 1 + 4 + 8

这就是(倍增的思想).
上面所说的 凑成一个数, 在实际问题中 对应为:
… 我们从a点, 跳跃n步, 到达b点; 转换为: 将n进行2进制拆分, 比如: n = 1 + 4 + 8
… 则, 跳8步, 然后跳4步, 最后跳1步

应用

倍增有两个应用: (1, 可重复覆盖问题) (2, 跳步)

---

可重复贡献问题

我们要查询一块区域A内的元素性质, 可以将该区域 用两块区域B C来替代
(这两个区域, 可以包含相同元素,但不可以 包含不属于A的元素) 即: $B\cup C=A,B\cap C\in A$
通过, 这个两个子区域的值, 可以推出 A的值.

换句话说, 假如我们要求的值 函数为:F( S) (表示S这个集合里所有元素的结果)
那么必须要满足: F ( { a , b , c , d } ) = F ( F ( { a , b , c } ) , F ( { b , c , d } ) ) F( \{a, b, c, d\}) = F( F( \{a, b, c\}), F( \{b, c, d\}) ) F({a,b,c,d})=F(F({a,b,c}),F({b,c,d}))

比如:

• RMQ: range min/max query区间最大/最小值.
  我们要查询[1, 2, 3, 4, 5]的RMQ, 可以得到[1, 2, 3, 4]的值 与 [2, 3, 4, 5]的值, 两者可以推出 [1, 2, 3, 4, 5]的值.
  不仅一维, 对于二维也适用! (比如二维, 一个矩阵, 他的两个 最大的正方形, 可以覆盖整个矩阵)
• 区间GCD: $gcd(a,b,c)=gcd(gcd(a,b),gcd(b,c))$
• 区间&操作: $(a\&b\&c)=(a\&b)\&(b\&c)$
  证明: 因为&操作, 可以按位拆分, 我们只分析其某一位即可.
  … 假如某一位, 各个元素的值为:a, b, c(要么是0, 要么是1); 我们要证明: a&b&c = (a&b&c)&a
  … 假如a = 1, ( 如果a&b&c = 1, 则再执行&a = &1后, 仍为1, 结果不变;)
  … ( 如果a&b&c = 0, 则再执行&a = &1后, 仍为0, 结果不变)
  … 假如a = 0, 则a&b&c必然为0, 则执行&a = &0后, 结果仍为0.
• 区间|操作: $(a|b|c)=(a|b)|(b|c)$
  … 假如某一位, 各个元素的值为:a, b, c(要么是0, 要么是1); 我们要证明: a|b|c = (a|b|c) | a
  … 假如a = 1, 则a|b|c 必然为1, 则再执行|a = |1后, 仍为1, 结果不变;
  … 假如a = 0, ( 如果 a|b|c为1, 则执行|a = |0后, 结果仍为1.) ( 如果a|b|c为0, 则执行| a = | 0后, 结果也不变)
  但, 区间异或^不满足: 可重复贡献问题!, 比如a = 1, (如果a^b^c = 0, 则再执行^a = ^1后, 变成了1, 结果改变了…)

---

算法: ST打表

假如 可重复贡献问题中, 所有查询的集合, 即F( S)中的集合S, 是一个 连续的范围 (一维的区间, 二维的矩阵)
则通常使用的解决办法是: ST打表

因此, ST打表, 可以处理, 我们上面讲的: (区间RMQ) (区间GCD) (区间&) (区间|) 等连续区间的 可重复贡献问题

要求的目标值, 也就是F()函数, 我们这里用Ans[]数组表示.
比如对于一维数组A[ n], 每次要求 F ( { A [ l ] , A [ l + 1 ] , . . . , A [ r − 1 ] , A [ r ] } ) F( \{ A[l], A[ l+1], ..., A[ r-1], A[r] \}) F({A[l],A[l+1],...,A[r−1],A[r]})的值
用 $Log(n)=p$ 表示: 最大的p, 满足: $2^p<=n$
则, 预处理$Ans[n][Log(n)+1]$数组,
其中, $Ans[ i][ j] $表示: F ( { A [ i ] , A [ i + 1 ] , . . . , A [ i + 2 j − 1 ] } ) F( \{ A[ i], A[i+1], ..., A[ i + 2^j - 1] \} ) F({A[i],A[i+1],...,A[i+2j−1]}) 的值
比如, $Ans[5][2]$ 表示: F ( { A [ 5 ] , A [ 6 ] , A [ 7 ] , A [ 8 ] } ) F( \{ A[5], A[6], A[7], A[8] \}) F({A[5],A[6],A[7],A[8]}) 的值

以下, 以(一维的) ST打表 为展示:

T A[ n];
T Ans[ n][ Log( n) + 1];

void build_ST(){
	FOR_( i, 0, n-1, 1){
		Ans[ i][ 0] = A[ i];
	}
	FOR_( pow, 1, Log( n), 1){
		FOR( i, 0, n-1, 1){
			int r = i + ( 1 << pow) - 1;
			if( r >= n){
				break;
			}
			int mid = i + (1 << (pow - 1)); //< 当前点, 跳(1 << (pow-1))步后的位置
			Ans[ i][ pow] = F( Ans[ i][ pow - 1], Ans[ mid][ pow - 1]);
		}
	}
}

T query( int _l, int _r){
	assert( _l <= _r);
	return Ans[ _l][ Log( _r - _l) + 1]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

跳步