前排提醒：由于我使用了某不知名图床，把图片全给搞丢了，导致观感较差，有空我会补回来。

大家好啊，我是 doooge，今天给大家带来的是：倍增&st表的详解。

$$\mathsf{倍增}\&st\mathsf{表详解}$$

1.什么是倍增&位运算

介绍倍增之前，我还需要介绍一下位运算。这一章很简单，如果你是 dalao 你也可以不看。

1.1 位运算

位运算是 c++ 底层的逻辑运算，位运算速度非常快，很多算法都可以用位运算优化。这里我就不细讲了，但是还是要提一些方便快捷的位运算技巧：

1. 判断 x 的第 i 位是否为 $1$：x&(1<<i)。
2. 判断 x 的第 i 位是否为 $0$：!(x&(1<<i))。
3. $2^i$：1<<i。
4. 将 x 的第 i 位变为 $1$：x|=1<<i
5. 将 x 的第 i 位变为 $0$：x&=~(1<<i)
6. 5. 将 x 的第 i 位 $01$ 翻转：x^=1<<i

注意：位运算的优先级很小，例如 1<<4+1 的答案其实是 1<<5，因为先算的是加法。

1.2什么是倍增

倍增，顾名思义，即为成倍成倍的增加（一般是两倍两倍的增加）。比如说有一个数列 a = { 1 , 2 , 4 , 8 , 16 , ⋯   } a = \{ 1,2,4,8,16,\cdots \} a={1,2,4,8,16,⋯} ，我们就可以说这个序列里的数是依次倍增的。所以，$1$ 倍增 $k$ 次也就等于 $2^k$。

倍增在哪里能用的上呢？最明显的就是二进制。

我们都知道，二进制的第 $i$ 位表示的是 $2^i$，比如说数字 $13$ 在二进制表示下是这样的：

位数	$3$	$2$	$1$	$0$
每一位所表示的数	$2^3$	$2^2$	$2^1$	$2^0$
这个二进制表示的数：$13$	$8$	$4$	$0$	$1$

于是，倍增算法就有了二进制拆分这个概念，二进制拆分是整个 st表 的精华。如果有学过多重背包的同学，对它一定不陌生吧。不过，与多重背包的二进制不同的是，对于数 $i$ ，要拆成若干个 $2^k$ 这样的数。什么？你说你听不懂？我们直接就来举个例子吧。

假设有一个数 $x$ ，有两种对它进行二进制拆分的方法：

法一：我们设一个数 $k=1$ 进行拆分：

• 若 $x\le k$，则记下答案 $k$，将 $x$ 减去 $k$，将 $k\times 2$。
• 若 $x<k$，将 $k÷2$。
• 这样一直重复到 $x=0$，拆分即完成。

法二：遍历 $x$ 二进制下的每一位，若第 $i$ 位在二进制下为 $1$，则记下这个 $i$ 所表示的数（也就是 $2^i$）。

两种拆法对于 $13$ 拆分的结果：

法一： { 1 , 2 , 4 , 4 , 2 } \{1,2,4,4,2\} {1,2,4,4,2}
法二： { 8 , 4 , 1 } \{8,4,1\} {8,4,1}

两种方法的代码：

法一：

void chai(int x){
	int k=1;//设数k进行拆分
	while(x>0){
		if(x>=k){
			cout<<k<<endl;//记录答案
			x-=k,k<<=1;//这里的<<=1跟*2相等
		}
		else{
			k>>=1;//这里的>>=1跟/2相等
		}
	}
	return;
}

法二：

void chai(int x){
	for(int i=30;i>=0;i--){//注意i要到0
		if(x&(1<<i)){//判断第i位是否有数
			cout<<(1<<i)<<endl;//记录答案
		}
	}
	return;
}

正片：2.st表的构造

st表是一个经典的倍增思想的数据结构，可以高效求解静态区间的问题，十分实用。

注意：st表 是一个预处理的数据结构，所以它是一个离线算法。

2.1 st表的思想

st表 是一种奇妙的数据结构，它用于求解静态区间最值问题（也叫 RMQ），它由一个二维数组构成。st表 有着非常多的种类，比如说求区间最大最小的 st表，求区间和的 st表，求区间 $\gcd$ 的st 表。

$s{t}_{i,j}$ 表示以 $i$ 做起点以及它往后 $2^j$ 个数中间 $a_k$ 的最值（$i\le k\le i+2^j-1$）。如果你写的 st表 是求区间最大值的 st表，那么 $s{t}_{i,j}$ 就是存储着以 $i$ 做起点以及它往后 $2^j$ 个数的最大值。求最小值和求和的原理是一样的。

假设数组 a = { 0 , 13 , 14 , 4 , 13 , 1 , 5 , 7 } a=\{0,13,14,4,13,1,5,7\} a={0,13,14,4,13,1,5,7} 和一个最大值 st表。那么 $s{t}_{1,0}$ 保存的就是 $a_1$ 的值 $0$，$s{t}_{1,1}$ 保存的是 $a_1$ 至 $a_2$ 的最大值 $13$，$s{t}_{1,2}$ 保存的是 $a_1$ 至 $a_4$ 的最大值 $14$，以此类推。

(来源oiwiki，侵删)

知道了这个概念，我们就来手推一下 $s{t}_{i,j}$ 的值吧！

$j=0$	$0$	$13$	$14$	$4$	$13$	$1$	$5$	$7$
$j=1$	$13$	$14$	$14$	$13$	$13$	$5$	$7$	无
$j=2$	$14$	$14$	$14$	$13$	$13$	无	无	无
$j=3$	$14$	无	无	无	无	无	无	无

由于 st表 中 $j$ 表示的是长度为 $2^j$ 的区间，所以 $j$ 的范围只有 $0$ 到 $\lfloor \log n\rfloor$，而 $i$ 表示的是 $1$ 到 $n$ 中间的任意一个起点，所以 st表的空间复杂度就是：
$$O(n\log n)$$

2.2 st表的构造

我们要怎样快速的求出 st表 中间的值呢？请看这张图：

(自己画的，很丑见谅)

我们会发现，$s{t}_{i,j}$ 由 $s{t}_{i,j-1}$ 和 $s{t}_{i+2^{j-1},j-1}$ 组成。也就是说，假设有一个 st表 是求区间最大值的，那么从 $a_i$ 到 $a_{i+2^j-1}$ 的最大值可以拆分成从 $a_i$ 到 $a_{i+2^{j-1}-1}$ 的最大值和从 $a_{i+2^{j-1}}$ 到 $a_{i+2^j-1}$ 的最大值，而然，拆分出的两个区间刚好对应着 $s{t}_{i,j-1}$ 和 $s{t}_{i+2^{j-1},j-1}$ 这两个区间（仔细想想）。

所以，我们就不难得到一个构建 st表 的代码：

for(int j=1;j<=lg[n];j++){
//st[i][0]直接用a[i]进行赋值或者直接输入
    for(int i=1;i<=n-(1<<j)+1;i++){
    //如果i循环到n的话，i+2j-1的区间范围就会越界（RE），所以这里要控制区间范围为n-2^j+1
        st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);//注意这里求的是最大值
    }
}

至于构建 st表 的复杂度，根据你的求区间最值的操作有关。如果要求的是区间加和或最大最小值，st表 的时间复杂度就是 st表 要遍历的项数，也就是：
$$O(n\log n)$$

如果是要求区间 $\gcd$，那么因为求两个数的 $\gcd$ 本来就要 $\log w$ 来求（$w$ 表示两个数的值域），所以构建的时间复杂度就是：
$$O(n\log n\log w)$$

2.3 st表构造的其他代码

在这里附上求区间和和区间 $\gcd$ 的 st表 的构建代码：

区间和：

for(int j=1;j<=log2(n);j++){
    for(int i=1;i<=n-(1<<j)+1;i++){
      st[i][j]=st[i][j-1]+st[i+(1<<(j-1))][j-1];
    }
}

区间 $\gcd$：

for(int j=1;j<=log2(n);j++){
	for(int i=1;i<=n-(1<<j)+1;i++){
  		st[i][j]=__gcd(st[i][j-1],st[i+(1<<(j-1))][j-1]);
	}
}

3.st表的查询

读到这里，聪明的读者不禁会问：“求 st表 个东西要干嘛？”别急，等会你就知道了。

考虑对 $l$ 到 $r$ 的区间求和，我们可以把它拆分成若干个长度为 $2^k$ 的区间。这是你发现了什么？诶，这不就是二进制拆分吗？没错，我们来举一个例子：

区间 $[5,18]$：拆成 $[5,5]$，$[6,7]$，$[8,11]$，$[12,15]$，$[16,17]$ 和 $[18,18]$。

值得一提的是，这里的二进制拆分与第一章说的有所不同，这里求的是区间值和：

int query(int l,int r){
	int k=0,ans=0;//与之前不同的是，之前的数2^k被如今的k取代 
	while(l<r){
		if(l+(1<<k)<=r){ 
		//这里的k代表的是2^k，所以写1<<k 
			ans+=st[l][k],l+=(1<<k);//更新答案和左端点
			k++//k++=2^k*2 
		}
		else{
			k--;//k--=2^k/2
		}
	}
	return ans;
}

这样的查询的时间 $O(\log n)$，但是这并不是 st表 的重点，重点是将查询优化至 $O(1)$。

4.st表优化查询

st表 的查询并不都是 $O(\log n)$ 部分查询其实是可以优化的，比如说求区间最大值。

4.1 查询优化的思路

考虑找出一个最大的 $2$ 的正整数次方为 $len$，使得两个长度为 $len$ 的区间能覆盖 $l$ 到 $r$ 这个区间。

显然：
$$len=2^{\lfloor {\log }_2(r-l+1)\rfloor }$$
且：
$$2\times len\ge r-l+1$$

可以看下图理解：

我们会发现，这两个长度为 $len$ 的区间分别覆盖在 $[l,l+2^{len}-1]$ 和 $[r-2^{len}+1,r]$ 这两个区间是一定能够完全覆盖住 $[l,r]$ 区间的。

所以！我们就可以通过这两个区间来求出区间最大值。也就是：
$$k=\lfloor {\log }_2(r-l+1)\rfloor$$
$$\max [l,r]=\max (s{t}_{l,k},s{t}_{r-2^k+1,k})$$

这时聪明的读者就会发现，这两个小的区间中间相交了。所以，区间求和并不能让查询优化成 $O(1)$。

4.2 查询优化后代码

区间最大值：

int query(int l,int r){
    int len=log2(y-x+1);
	return max(st[x][len],st[y-(1<<len)+1][len]);
}

区间最小值：

int query(int l,int r){
    int len=log2(y-x+1);
	return min(st[x][len],st[y-(1<<len)+1][len]);
}

区间 $\gcd$：

int query(int l,int r){
    int len=log2(y-x+1);
	return __gcd(st[x][len],st[y-(1<<len)+1][len]);
}

注意：由于求 $\gcd$ 本来就需要 $O(\log w)$ 的时间复杂度，所以优化后的查询的时间复杂度一样是 $O(\log w)$ 的。

4.3 优化 ${\log }_2$ 的常数

在前面的代码中，${\log }_2$ 这个函数我都用了 c++内置的 log2() 函数来写，但是 c++ 的 log2() 函数时间上来说的常数很大，所以我们可以把它预处理出来，下面代码中的 lg[i] 就表示着 $\lfloor {\log }_{2}i\rfloor$ 的值。

for(int i=1;i<=n;i++){
    lg[i]=log2(i);
}

或者是这个代码：

for(int i=2;i<=n;i++){
    lg[i]=lg[i>>1]+1;
}

论常数，第二个方法的代码的时间会快一点，但也没有多大的区别。

5.st表的完整代码（区间最大值）

#include<bits/stdc++.h>
using namespace std;
int st[100010][30],lg[100010];
int query(int l,int r){
    int len=lg[r-l+1];
    return max(st[l][len],st[r-(1<<len)+1][len]);
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>st[i][0];
	}
	for(int i=2;i<=n;i++){
		lg[i]=lg[i>>1]+1;
	}
	for(int j=1;j<=lg[n];j++){
		for(int i=1;i<=n-(1<<j)+1;i++){
			st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
		}
	}
	while(m--){
		int x,y;
		cin>>x>>y;
        cout<<query(x,y)<<'\n';
    }
	return 0;
}

6.例题

6.1 T1-P1198 [JSOI2008] 最大数

6.1.1 题目内容

现在请求你维护一个数列，要求提供以下两种操作：

1. Q L，查询当前数列中末尾 $L$ 个数中的最大的数。
2. A n，将 $n$ 加上 $t$，其中 $t$ 是最近一次查询操作的答案（如果还未执行过查询操作，则 $t=0$），并将所得结果对一个固定的常数 $D$ 取模，将所得答案插入到数列的末尾。

6.1.2 思路&代码：

这里只考虑 st表 的做法。查询就不讲了，这里重点将插入操作。

考虑插入数字到最后一个（记这里的下标为 $n$，数字为 $k$）会对 $st$ 数组造成什么影响。我们发现将数插入在数组末尾，只会对：
$$s{t}_{n-2^j+1,j}(j\le \lfloor lo{g}_{2}n\rfloor )$$
造成影响。所以我们只要遍历 $j$ 然后修改就可以了。

部分代码：

st[++n][0]=(x+t)%P;//j=0的情况直接处理
for(int i=1;i<=lg[n];i++){
    int pos=n-(1<<i)+1;//对于每一个j，会造成影响的只有st[n-2^i+1][j]
    st[pos][i]=max(st[pos][i-1],st[pos+(1<<(i-1))][i-1]);
}

完整代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int st[200010][30],lg[200010];
signed main(){
	int n=0,t=0,m,P;
	cin>>m>>P;
	for(int i=2;i<=m;i++){
		lg[i]=lg[i>>1]+1; 
	}
	while(m--){
		char op;
		int x;
		cin>>op>>x;
		if(op=='A'){
			st[++n][0]=(x+t)%P;
			for(int i=1;i<=lg[n];i++){
				int pos=n-(1<<i)+1;
				st[pos][i]=max(st[pos][i-1],st[pos+(1<<(i-1))][i-1]);
			}
		}
		else{
			int len=lg[x];
			t=max(st[n-x+1][len],st[n-(1<<len)+1][len]);
			cout<<t<<'\n'; 
		}
	}
	return 0;
}

6.2 T2-P9032 [COCI2022-2023#1] Neboderi

6.2.1 题目内容

[COCI2022-2023#1] Neboderi

有 $n$ 个数 $a_1,a_2,a_3,\cdots ,a_n$，现在请你求出一个长度不小于 $k$ 的区间 $[l,r]$，使得 ${\sum }_{i=l}^r{a}_i\times \gcd (a_l,a_{l+1},a+l+2,\cdots ,a_r)$ 最大。

6.2.2 思路&代码

本蒟蒻并不会写 $O(n(\log n{)}^2)$ 的时间复杂度的代码，用 $O(n(\log n{)}^3)$ 卡过去的。

首先，我们要明白两个特性：

对于若干个区间 $[l_i,r_i]$，如果这些区间的左端点都固定到$l$上，那么随着 $r$ 的增加，$\gcd (l,\cdots ,r)$ 单调不增。

)

而且，对于这样的固定 $l$ 区间，区间的 $\gcd$ 最多只有 $\log n$ 种。这个是可以证明的，但篇幅较长，我这里就不多提了。

于是！我们就可以遍历左端点 $i$，把 $[i,i+1],[i,i+2],\cdots ,[i,n]$ 这些区间给分成若干块，每个块中的任意一个下标 $x$，$[i,x]$ 中 $a_i\gcd$ 都相等，且总块数不会超过 $\log n$。

假设有一段区间：$[12,12,16,8,4,2,6,3,1]$。我们可以把它分成 $[12,12]$ 一块，$[16,8,4]$ 一块，$[2,6]$ 一块，$[3,1]$ 一块。（这里可以仔细想想）

我们又知道，每个块中每个下标 $x$，$[i,x]$ 中 $a_i\gcd$ 都相等，而且 $x$ 越大，${\sum }_{j=i}^x{a}_j$ 也会越来越大，那么每块中只有一个最优的答案，就是这个块的最后一个 $x$，因为此时 $a_i$ 至 $a_x$ 的和最大。

我们可以枚举 $i$ （$1\le i\le n$）作为左端点，然后寻找不同的块，找到每一个块端点，记录最佳答案。

至于 $[l,r]$ 的和，我们可以使用前缀和进行优化。

代码：

#include<bits/stdc++.h>
using namespace std;
int a[1000010],lg[1000010],st[1000010][30];
long long s[1000010];
int query(int l,int r){
	int len=lg[r-l+1];
	return __gcd(st[l][len],st[r-(1<<len)+1][len]);
}
int mid_check(int i,int l2,int n,int x){
	int l=l2,r=n;
	while(l<r){
		int mid=(l+r+1)>>1;
		if(query(i,mid)==x)l=mid;
		else r=mid-1;
	}
	return l;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	long long n,m,ans=0;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		st[i][0]=a[i],s[i]=s[i-1]+a[i];
	}
	for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1;
	for(int j=1;j<=lg[n];j++){
		for(int i=1;i<=n-(1<<j)+1;i++){
			st[i][j]=__gcd(st[i][j-1],st[i+(1<<(j-1))][j-1]);
		}
	}
	for(int i=1;i<=n;i++){
		if(i+m-1>n)break;
		int r=mid_check(i,i+m-1,n,a[i]);
		ans=max(ans,1ll*query(i,r)*(s[r]-s[i-1]));
		while(r<n){
			int l=r+1;
			r=mid_check(i,l,n,query(i,l));
			ans=max(ans,1ll*query(i,r)*(s[r]-s[i-1]));
		}
	}
	cout<<ans<<'\n';
}

6.作业

1. P7333 [JRKSJ R1] JFCA
2. P10059 Choose

7.闲话

蒟蒻不才，膜拜大佬，文章如果有错字或别的错误，欢迎各位大佬在评论区指出。