浅谈 ST 算法

注：本文的确是浅谈，因为觉得不难 -.-

在我们求解 RMQ （区间最大（小）值）的时候，如果没有修改操作（就是离线），那么 ST 算法是很好的选择

空间按复杂度 (O(n log n)) ，时间复杂是预处理的 (O(nlog n)) 和 查询的 (O(1))，其实用到的思想是 dp 和倍增

倍增的思想就是通过 2 的幂次来增快枚举，其实就是一个小dp。

定义

(f[i][j]) 表示 在 (i) 下标开始长度为 (2^j) 的区间了的最大（小）值

方程

[f[i][j] = max or min(f[i][j - 1],f[i + 2 ^{j - 1}][j - 1]) ]

所求

假设查询区间 ([l,r]) 的 RMQ 那么有 (ans = max or min (f[l][log_2 (r - l + 1)], f[r- 2^{log_2 (r-l + 1)} + 1][log_2(r - l + 1)]))

于是一个简单的 dp 就可以完成。确实没什么好说的

#define _CRT_SECURE_NO_WARNINS

#include <bits/stdc++.h>

using namespace std;

template <typename T>
inline T read()
{
	T x = 0;
	char ch = getchar();
	bool f = 0;
	while(ch < '0' || ch > '9')
	{
		f = (ch == '-');
		ch = getchar();
	}
	while(ch <= '9' && ch >= '0')
	{
		x = (x << 1) + (x << 3) + (ch - '0');
		ch = getchar();
	}
	return  f? -x : x;
}

template <typename T>
void put(T x)
{
	if(x < 0)
	{
		x = -x;
		putchar('-');
		}
	if(x < 10) {
		putchar(x + 48);
		return;
	}
	put(x / 10);
	putchar(x % 10 + 48);
	return ;
}

const int Maxn = 1e5 + 11;

int n, q, f[Maxn][18], l, r, bin[22];

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

int main()
{
	n = read <int> ();
	q = read <int> ();
	for(int i = 1; i <= n; ++i) f[i][0] = read <int> ();
	int tmp1 = log2(n);
	for(int i = 1; i <= tmp1; ++i)
	{
		int tmp = 1 << i;
		for(int j = 1; j <= n - tmp + 1; ++j) f[j][i] = max(f[j][i - 1], f[j + tmp / 2][i - 1]);
	}
	while(q--)
	{
		put(query(read <int> (), read <int> ()));
		putchar('
');
	}
	return 0;
}

据说有一种求 RMQ 的方法可以做到 (O(n)) 预处理，(O(1)) 查询,而且支持在线，好像叫约束 RMQ......QAQ