Doubled and sparse tables

倍增、ST、RMQ

1、倍增

Any integer can be represented as several2的次幂项之和.例如：

• 整数5,其二进制表示为101,该二进制数从右向左第0、2位均为1,则5=2+20

• 整数26,其二进制表示为11010,该二进制数从右向左第1、3、4位均为1,则 $26=2^4+2^3+2^1$ .也就是说,2The power terms of can be spelled to any desired value.

倍增,顾名思义就是成倍增加.若问题的状态空间特别大,则一步步递推的算法复杂度太高,可以通过倍增思想,只考察2integer power position of ,快速缩小求解范围,直到找到解.

2、ST

ST（Sparse Table,稀疏表）The algorithm adopts the idea of ​​multiplication,在 $O(nlogn)$ 时间构造一个二维表之后,可以在 $O(1)$ 时间在线查询 $[l,r]$ 区间的最值,有效解决 在线RMQ（Range Minimum/Maximum Query,区间最值查询）问题.如何实现呢？

设 $F[i,j]$ 表示 $[i,i+2^j-1]$ 区间的最值,区间长度为 $2^j$.

根据倍增思想,长度为 $2^j$ The interval can be divided into two lengths $2^{j-1}$ 的子区间,Then find the maximum value of the two subintervals.

递推公式：$F[i,j]=max(F[i,j-1],F[i+2^{j-1},j-1])$

2.1 ST表的创建

若 $F[i,j]$ 表示 $[i,i+2^j-1]$ 区间的最值,区间长度为$2^j$,则和 $j$ What is the value range of ?

若数组的长度为 $n$ ,Maximum interval length $2^k\le n<2^{k+1}$,则 $k=\lfloor lo{g}_{2}n\rfloor$, 比如：

• n=8时k=3,
• n=10时k=3.

在程序中,k=log2(n), Common expressions are also available k=log(n)/log(2),log()表 show e为底的自然对数.

void ST_create() {
    
	for(int i=1; i<=n; i++) {
    
		F[i][0]=a[i];// 区间[i,i]的最值,interval length bits2^0
	}
	int k=log(n)/log(2.0);
	for(int j=1; j<=k; j++) {
    
		for(int i=1; i<=n-(1<<y)+1; i++) {
    
			F[i][j]=max(F[i][j-1],F[i+(1<<j-1)][j-1])
		}
	}
}

例如,有10个元素 $a[\mathrm{1..10}]=5,3,7,2,12,1,6,4,8,15$,Create a query for the maximum valueST表.$F[i,j]$ 表示 $[i,i+2^j-1]$ 区间的最值,区间长度为2.

2.2 ST表查询

若查询 $[l,r]$ 区间的最值,则首先计算 $k$ 值,和前面的计算方法相同,区间长度为 $r-l+1$,$2^k\le r-l+1<2^{k+1}$, 因此 $k=log2(r-l+1) $.

若查询区间的长度大于或等于 $2$ 且小于 $2^{k+1}$ ,则根据倍增思想,可以将查询区间分为两个查询区间,取两个区间的最值即可.The two intervals are from backward $2^k$ 个数及从 $r$ 向前的 $2^k$ 个数,这两个区间可能有重叠,但对求最值没有影响.

int ST_query(int l, int r){
    
	int k=log2(r-l+1);
	return max(F[l][k], F[r-(1<<k)+1][k])
}

3、RMQ

RMQ(区间最值查询)There are multiple solutions to the problem,Use a segment tree and ST解决RMQThe comparison of the problems is as follows：

• The time for segment tree preprocessing is $O(nlogn)$,查询的时间为 $O(logn)$ ,支持在线修改
• STThe preprocessing time is $O(nlogn)$,查询的时间为 $0(1)$ ,不支持在线修改.