ST表

ST表

一、引入

如何解决区间最值问题？
最容易想到的就是暴力枚举，但是很明显，速度过于慢，所以引入ST表

二、ST表

我们令f[i][len]表示以i开头长度为1<<len的最大值
由此可以突出初始值为f[i][0] = a[i]
接下来思考转移，我们就是要把f[i][len]拆成两个更容易就觉得问题。那么就可以推出f[l][len] = max(f[l][len-1],f[l+(1<<(len-1))][len-1])，因为最大值是可以重叠的

for (int i = 1;i <= n;i++) f[i][0] = a[i];//初始化
for (int len = 1;1<<len <= n;len++)
{
	for (int l = 1;l+(1<<len)-1 <= n;l++)
	{
		f[l][len] = max(f[l][len-1],f[l+(1<<(len-1))][len-1]);//转移
	}
}

三、应用

1.实现添加操作

只需要枚举长度就可以算出开头，这样直接转移

2.双关键字问题

与上面模板几乎没区别，只需要在取max或min是改变即可