学习笔记索引

众所周知，scy5赛时在P10059 Choose写了个滑动窗口骗 \(40\) 分，但是狂 WA 不止，丢掉了 \(rk155\)，于是就有了下面这两张口吐芬芳的图：

听说这题可以用ST表做，但他不会，于是他就来学倍增乐。

省流：被吊打了

更改日志

2024/01/16：开坑。

倍增原理

设做一件事有 \(n\) 个步骤。

模拟想法：我们可以一个一个步骤去做，时间复杂度 \(\mathcal{O}(n)\)。

有满足条件为：用第 \(x\) 步的结果可以推出第 \(2 \times x\) 步的结果。

那么我们可以预处理出 \(2\) 的幂次步的结果，然后将 \(n\) 二进制拆分。

如 \(n=7\) 时，等于第 \(1\) 步 \(+\) 第 \(2\) 步 \(+\) 第 \(4\) 步。

时间复杂度 \(\mathcal{O}(logn)\)，相较于模拟想法更优。

理解倍增

我们拿快速幂来当作例子（应该都会）。

大意

求 \(a^b \bmod p\)。

\(0\le a,b < 2^{31}\)，\(a+b>0\)，\(2 \leq p \lt 2^{31}\)。

数据太大，模拟的时间复杂度为 \(\mathcal{O}(b)\)，不可行。

其实快速幂也可以用倍增优化。

可以发现，求幂次就满足倍增的条件：用第 \(x\) 步的结果可以推出第 \(2 \times x\) 步的结果。

因为 \(a^x\) 和 \(a^{2\times x}\) 次方有关系，\(a^{2\times x} = a^x \times a^x\)。

然后就可以先求出 \(a^1,a^2,a^3...\) 的值。

最后求 \(a^b\) 时，将 \(b\) 二进制拆分。

那么，如 \(b=13\)，\(13\) 可以分解为 \(8+4+1\)，那么答案就是 \(a^8 \times a^4 \times a^1\)。

二进制拆分应该都会，就不写了（懒）

二进制拆分就是算出 \(b\) 的二进制然后如果一位是1就拆出一个这一位相应的数啦！

ST表（RMQ）

P3865 【模板】ST 表

题目描述

给定一个长度为 \(N\) 的数列，和 $ M $ 次询问，求出每一次询问的区间内数字的最大值。

输入格式

第一行包含两个整数 \(N,M\)，分别表示数列的长度和询问的个数。

第二行包含 \(N\) 个整数（记为 \(a_i\)），依次表示数列的第 \(i\) 项。

接下来 \(M\) 行，每行包含两个整数 \(l_i,r_i\)，表示查询的区间为 \([l_i,r_i]\)。

输出格式

输出包含 \(M\) 行，每行一个整数，依次表示每一次询问的结果。

提示

对于 \(30\%\) 的数据，满足 \(1\le N,M\le 10\)。

对于 \(70\%\) 的数据，满足 \(1\le N,M\le {10}^5\)。

对于 \(100\%\) 的数据，满足 \(1\le N\le {10}^5\)，\(1\le M\le 2\times{10}^6\)，\(a_i\in[0,{10}^9]\)，\(1\le l_i\le r_i\le N\)。

解法

这题先考虑暴力，每次找一遍区间最大值，时间复杂度 \(\mathcal{O}(n \times m)\)，不可能通过如此大的数据。

那么我们去想：这题是否满足倍增的条件：用第 \(x\) 步的结果可以推出第 \(2 \times x\) 步的结果？

答案是肯定的，因为我们可以知道，如果我们知道了两个相邻区间的最大值，那么这个大区间的最大值就是两者取 \(\max\)，那么就可以知道，用两个相邻的长度为 \(2\) 的区间可以求出长度为 \(4\) 的区间，两个相邻的长度为 \(4\) 的区间可以求出长度为 \(8\) 的区间，以此类推……

那么定义一个数组 \(f_{i,j}\) 表示从位置 \(i\) 开始，长度为 \(2^j\) 的区间中的最大值是多少。

首先，所有的 \(f_{i,0} = a_i\)，因为就是从位置 \(i\) 开始，长度为 \(1\) 的区间中的最大值是多少，那肯定就是他自己。

然后，当 \(j>0\) 时，因为 \(2^j=2^{j-1}+2^{j-1}\)，所以可以将长度为 \(2^j\) 的区间拆为两个长度为 \(2^{j-1}\) 的区间，那么就转移就是（下面将 \(f_{i,j}\) 写为 \(f(i,j)\)）：

这样预处理的时间复杂度为 \(\mathcal{O}(nlogn)\)。

那么，预处理就好了。

然后是调用。

那么我们就对区间长度（就是 \(r-l+1\)）进行二进制分解，设区间长度为 \(7\)，那么可以拆成 \(1+2+4\)，可以将区间 \([2,8]\) 拆为三个区间 \([2,2],[3,4],[5,8]\)，这三个区间，分别对应 \(f(2,0),f(3,1),f(5,2)\)。

然后二进制拆分即可。

CODE：

#include<bits/stdc++.h>
using namespace std;
int n,m,l,r,a[100010],ST[100010][20]; 
int qpow(int a,int b){//快速幂
	int ret=1;
	while(b){
        if(b%2!=0){
			ret=ret*a;
		}  
        a=a*a,b/=2;
    }return ret;
}int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		ST[i][0]=a[i];//初始化
	}for(int j=1;j<=20;j++){//枚举幂次
		for(int i=1;i+qpow(2,j)-1<=n;i++){//枚举起点
			ST[i][j]=max(ST[i][j-1],ST[i+qpow(2,j-1)][j-1]);//转移
		}
	}for(int i=1;i<=m;i++){
		scanf("%d%d",&l,&r);
		int len=r-l+1,ret=-1,cnt=0;
		for(int j=0;j<20;j++){
			if(len%2==1){//若这一位为一
				ret=max(ret,ST[l+cnt][j]);//那么就尝试更新
				cnt+=qpow(2,j);//下一个拆出的区间
			}len/=2;//去掉这一位
		}printf("%d\n",ret);
	}return 0;
}

咕咕咕