[DataStructure]Sparse Table

对于不需要支持频繁更新的range query，我们很多时候可以用更有效率的数据结构来储存。比如区间和的话，如果更新不频繁，我们只需要存presum即可，然后每次查询用两个presum相减，这样可以用O(n)的空间达到O(1)的查询速度。对于其他的问题也有类似的思路，比如Range Minimum Query(RMQ)问题，虽然我们没有办法用线性空间达到常数空间的查询速度，我们可以用Sparse Table O(n * log n)的空间达到O(1)的查询速度。
对于长度为n的数组，Sparse Table的结构(log2(n) + 1) * n的一个matrix，ST[i][j]存的是从j开始的长度为2^i的区间的最小值，比如对于下图的array：

对应的Sparse Table的结构为：

因为RMQ的性质，即使我们查询两个overlapping的区间i1和i2，那么我们仍然有RMQ(i1 U i2) = min(RMQ(i1), RMQ(i2))。假设查询区间为[i, j]，k = floor(log2(j - 1 + 1))，那么我们只需要查询min(ST[k][i], ST[k][j - 2^k + 1])。代码如下：

	class RMQ {
	public:
	RMQ(vector<int> nums) {
	n = nums.size();
	if (!n)return;
	m = static_cast<int>(log(n) / log(2.0)) + 1;
	m_st = vector<vector<int>>(m, vector<int>(n, 0));
	m_st[0] = nums;
	init(nums);
	}
	int query(int i, int j) {
	int len = j - i + 1, k = static_cast<int>(log(len) / log(2.0));
	return min(m_st[k][i], m_st[k][j - (1 << k) + 1]);
	}
	private:
	int n, m;
	vector<vector<int>> m_st;//sparse table
	void init(vector<int>& nums)
	{
	for (int i = 1; i < m; ++i)
	{
	for (int j = 0; j <= n - (1 << i); ++j)
	{
	m_st[i][j] = min(m_st[i - 1][j], m_st[i - 1][j + (1 << (i - 1))]);
	}
	}
	}
	};

view raw RMQ.cpp hosted with ❤ by GitHub

另外，RMQ与LCA(Lowerst Common Ancester)问题有紧密的联系。如果我们需要频繁地对树中的任意两个节点进行LCA的查询，RMQ可以给我们很大的帮助，具体请参考这篇文章。