ST表板子 类似归并的有条理暴力 sparse-table

目录

 ST表部分的代码：

使用示范：

1.原理是“倍增”，直到两个长度为1的就可以合成一个长度为2的，两个2合成4，两个4合成8。

2.最后使用时没必要追求“正好匹配”，可以在范围内取多点：

比如看4~8长度为5（45678），我们取长度为4，看4~7与5~8的最大值哪个更大即可。

 ST表部分的代码：

//ST表
	vector<vector<int>>st(30,vector<int>(n+1));//len = 2的i次方
	int len = 1;
	for (int pow = 0; len <= n; pow++, len *=2)
	{
		for (int left = 1; left <= n- len+1; left++)
		{
			if (pow == 0)
				st[0][left] = arr[left];
			else
			{
				st[pow][left] = max(st[pow - 1][left], st[pow - 1][min(left + len / 2,n)]);
			}
		}
	}

使用示范：

void solve()
{
	int n, m;
	cin >> n >> m;
	vector<int>arr(n+1);
	for (int i = 1; i <= n; i++)
	{
		cin >> arr[i];
	}
	//ST表
	vector<vector<int>>st(30,vector<int>(n+1));//len = 2的i次方
	int len = 1;
	for (int pow = 0; len <= n; pow++, len *=2)
	{
		for (int left = 1; left <= n- len+1; left++)
		{
			if (pow == 0)
				st[0][left] = arr[left];
			else
			{
				st[pow][left] = max(st[pow - 1][left], st[pow - 1][min(left + len / 2,n)]);
			}
		}
	}
	for (int i = 1; i <= m; i++)
	{
		int l, r;
		cin >> l >> r;
		//l+len-1<=r	len = 2的k次方
		//len <= r-l+1
		//k <= log(r-l+1);
		int k = log2(r - l + 1);
		cout << max(st[k][l], st[k][r-pow(2,k)+1]) << endl;
	}
}