理论：如何设计

需求：要解决的问题

对于一些题目，他们要求你计算一个区间内的最小值，没有操作，但是询问次数特别多，以至于树状数组和线段树 $O(m\log n)$ 的时间复杂度已经不够优秀，我们需要引入新的数据结构。

构造：寻找合理方案

同样的，我们说过，数据结构是时空平衡的，想要把单次询问复杂度降下来，就需要更高的预处理和空间复杂度。根据我们数据结构的根本是分组的思想，我们需要重新修改分组。

我们思考一下，理想状态是什么？理想状态是我们预处理出来的值可以直接拿出来用，或者经过 $1$ 次运算可以得出。
我们可以和两个极端比较一下。

预处理 单次
数组 读入 $O(n)$ for 一遍 $O(n)$
预处理出所有区间最值 $O(n^2)$ $O(1)$
理想数据结构 不知道 由于查询次数极多，所以必须需要单次 $O(1)$ 的算法

首先我们坑定得是 $1$ 对多的分组方式，我们可以打表看看

对于序列 $a[10] = [ 1, 4, 7, 3, 2, 8, 5, 9, 6, 10 ]$ 可以得出如下表格。

区间 $[l,r]$ 1 2 3 4 5 6 7 8 9 10
1 1 1 1 1 1 1 1 1 1 1
2 4 4 3 2 2 2 2 2 2
3 7 3 2 2 2 2 2 2
4 3 2 2 2 2 2 2
5 2 2 2 2 2 2
6 8 5 5 5 5
7 5 5 5 5
8 9 6 6
9 6 6
10 10

首先，作为最基础的，每一个节点的单独值，都是要的。考虑 $[1, 2]$ 要不要，发现 $[1,2]$ 可以由 $[1, 1]$ 和 $[2, 2]$ 拼出来，但是如果不带的话，$[1, 3]$ 就不能 $1$ 次实现，所以 $[1, 2]$ 要带，同理，形如 $[l, l+1]$ 的区间都要带。可得下表：（加粗表示要带）

区间 $[l,r]$ 1 2 3 4 5 6 7 8 9 10
1 1 1 1 1 1 1 1 1 1 1
2 4 4 3 2 2 2 2 2 2
3 7 3 2 2 2 2 2 2
4 3 2 2 2 2 2 2
5 2 2 2 2 2 2
6 8 5 5 5 5
7 5 5 5 5
8 9 6 6
9 6 6
10 10

同样的，考虑 $[1, 3]$ 要不要带，它可以被拼出来，而且如果不带，$[1, 4]$ 也可以一次拼出来，所以不用。而 $[1,4]$ 如果不带，$[1, 5]$ 就拼不出来。所以 $[1,3]$ 不带，$[1,4]$ 带。同理，形如 $[l, l+ 3]$ 的，都要带。

区间 $[l,r]$ 1 2 3 4 5 6 7 8 9 10
1 1 1 1 1 1 1 1 1 1 1
2 4 4 3 2 2 2 2 2 2
3 7 3 2 2 2 2 2 2
4 3 2 2 2 2 2 2
5 2 2 2 2 2 2
6 8 5 5 5 5
7 5 5 5 5
8 9 6 6
9 6 6
10 10

以此类推，下一个要带的就是形如 $[l, l + 7]$ 的了，如下表

区间 $[l,r]$ 1 2 3 4 5 6 7 8 9 10
1 1 1 1 1 1 1 1 1 1 1
2 4 4 3 2 2 2 2 2 2
3 7 3 2 2 2 2 2 2
4 3 2 2 2 2 2 2
5 2 2 2 2 2 2
6 8 5 5 5 5
7 5 5 5 5
8 9 6 6
9 6 6
10 10

观察刚刚的要的区间：$[l, l + 2^1 -1],[l, l+2^2 -1],[l,l+2^3-1]$ 。分组就显然了。

按照下标分组，将他的 $2^n$ 次幂分一组。

总结：何为倍增算法

倍增法（英语：$\tt binary\ lifting$），顾名思义就是翻倍。它能够使线性的处理转化为对数级的处理，大大地优化时间复杂度。

这个方法在很多算法中均有应用，其中最常用的是 $\tt RMQ$ 问题和求 $\tt LCA$（最近公共祖先）。

实现：如何编写

基础：基本结构

显而易见，首先是需要预处理，而预处理也十分简单。我们定义数组 $st[N][lg[N]]$ 因为我们是以 $2$ 的幂次分组，所以第二维只需要开 $\log n$ 的大小。首先从低次幂开始，因为递推的需要，从低次幂开始把每一位的值预处理出来以后在继续预处理。

查询的时候我们考虑如何查询，因为我们的目标是 $O(1)$ ，所以肯定不可以从 $1$ 开始 $2$ 次幂跳。由于对于最值操作，重复是没有问题的，所以就不难得出：

1
min(st[l][lg[r - l + 1]], st[r - (1 << (r - l + 1)) + 1][lg[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
24
25
int lg[100010];

struct ST{
	int st[100010][50];
	
	void Init(int n, int *a){
		lg[0]=-1;
		for(int i=1; i<=n; i++){
			lg[i]=lg[i>>1]+1;
		}
		for(int i=1; i<=n; i++){
			st[i][0]=a[i];
		}
		for(int j=1; j<=lg[n]; j++){
			for(int i=1; i+(1<<j)-1<=n; i++){
				st[i][j]=min(st[i][j-1], st[i+(1<<(j-1))][j-1]);
			}
		}
	}

	int ask(int l, int r){
		int len=lg[r-l+1];
		return min(st[l][len], st[r-(1<<len)+1][len]);
	}
}ST;

实践：例题推荐