想学习一下LCA倍增，先 ~~水一个黄题~~ 学一下ST表

ST表

介绍：

这是一个运用倍增思想，通过动态规划来计算区间最值的算法

算法步骤：

求出区间最值

回答询问

求出区间最值：

用 $f[i][j]$ 来存储从第 $j$ 个点开始，向后 $2 ^ i - 1$ 个点（共 $2 ^ i$ 个点）中的最值(包括本身）

利用二分法的思想，将区间 $[ j, ~j + 2 ^ i- 1 ]$ 平均（大概）分成两半

可以算出，区间 $[ j, ~j + 2 ^ i - 1 ]$ 的长度为 $2 ^ i$

所以一半的长度为 $2 ^ {i - 1}$

那么分成的两个区间就为 $[j, ~j + 2 ^ {i - 1} - 1 ]$ 和 $[ j + 2 ^ {i - 1}, ~j + 2 ^ i - 1 ]$ 。

毫无疑问，

\[f[i][j] = max（f[i - 1][j],~f[i - 1][j + (1 << i - 1)]） \]

这样递推式就出来了

现在来想一下：
$f[0][j]$ 就是从 $j$ 开始向后数第 $2 ^ 0 - 1$ 个点的最值，区间为 $[j,~j]$（区间不能这么写，这里请不要较真）

不用考虑，$f[0][j]$ 就是第 $j$ 个数本身

好了，现在边界也得出来了，可以开始 dp 了

上代码：

void prew() {
	for (int i = 1; i <= n; ++i) f[0][i] = a[i]; // 给边界赋值，a[i] 存的是数列的第 i 个数
	int kf = log2(n); // 得出数列最多可以向后跳几个 2 的幂，n 为数列长度
	for (int i = 1; i <= kf; ++i) { // 枚举区间的长度 2 ^ i
	      for (int j = 1; j + (1 << i) - 1 <= n; j++) // 枚举起点
		      f[i][j] = max(f[i - 1][j], f[i - 1][j + (1 << i - 1)]); // 递推式
	}
}

一个小问题：

由于 $log_2$ 运算可能会出现实数，而我们又用整数类型来存储，所以可能会出现两个区间不能完全覆盖整个区间的情况，得出的 $f[i][j]$ 不够精准

最简单的方法就是用两个区间覆盖

反正又没要求两个区间不能重叠~~

可以选用 $f[k][l]$ 和 $f[k][r-（1<<k）+1]$ 来覆盖 $f[l][r]$

所以 $$f[l][r] = max（f[k][l]，f[k][r -（1 << k）+ 1]）$$（$k$ 为区间 $[l,~r]$ 的长度的 $log_2$）

再上代码：

int ask(int l, int r) {
	int k = log2(r - l + 1); // 求出区间最大的 log2 值
	return max(f[k][l], f[k][r - (1 << k) + 1]); // 返回区间 [l，r] 的最大值
}

完整代码：

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#define MAXN 100010
#define int long long
using namespace std;
//-------------定义结构体-----------

//--------------定义变量------------
int f[31][MAXN], Log2[MAXN], a[MAXN]; // f[i][j]表示从 j 往后 2 ^ i - 1 个数中的最大值 
int n, m;
//--------------定义函数------------
inline int read() {
	int x = 0, f = 0; char ch = getchar();
	while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
	while (isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
	return f ? -x : x;
}
int max(int a, int b) {
	return a > b ? a : b;
}
int min(int a, int b) {
	return a < b ? a : b;
}
void swap(int &a, int &b) {
	a ^= b ^= a ^= b;
}
void pre() { // 预处理 dp
	Log2[0] = -1;
	for(int i = 1; i <= 100000; ++i) Log2[i] = Log2[i >> 1] + 1;
	for (int i = 1; i <= n; ++i) f[0][i] = a[i];
	for (int i = 1; i <= Log2[n]; ++i) {
		for (int j = 1; j + (1 << i) - 1 <= n; j++)
			f[i][j] = max(f[i - 1][j], f[i - 1][j + (1 << i - 1)]);
	}
}
int ask(int l, int r) { // 回答询问
	int k = Log2[r - l + 1];
	return max(f[k][l], f[k][r - (1 << k) + 1]);
}
//---------------主函数-------------
signed main() {
	int l, r, ans;
    n = read(); m = read();
    for (int i = 1; i <= n; ++i) a[i] = read();
    pre();
    for (int i = 1; i <= m; ++i) {
    	l = read(); r = read();
    	ans = ask(l, r);
    	printf("%d\n", ans);
    }
	return 0;
}

模板题：
洛谷P3865

【算法】ST表

ST表

介绍：

算法步骤：

完整代码：

推荐阅读