[Data Structure]Sqrt Decomposition

Sqrt Decomposition是支持range query和update的数据结构。用额外O(sqrt(n))的空间，可以将区间查询的时间复杂度提升为O(sqrt(n))，单点更新的时间复杂度是O(1)。
具体来讲我们将长度为n的array分为长度为k = ceil(sqrt(n))的block，分完之后剩下长度不足k的归为一个区间。如图所示(图片来自Geeks for Geeks)：

如果我们求的是range sum，那么sqrt数组每个存的就是对应区间的和。建sqrt数组的代码很简单，需要的空间是sqrt(n)。更新的话，非常简单，直接找到对于的sqrt的位置，加上相应的差值即可。
那我们如何查询呢？如果查询区间为正好覆盖sqrt数组，那么很简单，我们直接累加sqrt数组对应的值即可。比如我们查询[3,8]区间的和，那么我们直接将block1和block2相加即可，时间复杂度最差为O(m)，m是block的数量。那么如果查询区间不覆盖sqrt数组呢，显然对于不完全覆盖的部分，我们要去原数组中一个一个找并且求和，那么对于完全覆盖的部分，和第一种情况一样，如图所示(图片来自Geeks for Geeks)：

比如我们要查询[1,6]区间的和，我们要去原数组查询num[1], num[2], num[6]，我们在sqrt数组里查询sqrt[1]即可。时间复杂度分析的话，最差情况，原数组num我们要查询2 * (k - 1)个数，也就是首尾block正好只覆盖k - 1个元素，对于blocks的话，最坏我们要查O(m - 2)个，m为block的数量，那么总的查询数是3 * sqrt(n)，时间复杂度就为O(sqrt(n))，代码如下：

	class NumArray {
	public:
	NumArray(vector<int> nums) {
	n = nums.size();
	m_nums = nums;
	len = static_cast<int>(ceil(sqrt(n)));
	m_sq = vector<int>(len, 0);
	for(int i = 0; i < n; ++i)
	m_sq[i / len] += nums[i];
	}
	void update(int i, int val) {
	int diff = val - m_nums[i];
	m_nums[i] = val;
	m_sq[i / len] += diff;
	}
	int sumRange(int i, int j) {
	i = max(i, 0);
	j = min(j, n - 1);
	int startBlock = i / len, endBlock = j / len, sum = 0;
	if(startBlock == endBlock)
	{
	for(int k = i; k <= j; ++k)
	sum += m_nums[k];
	return sum;
	}
	for(int k = i; k < (startBlock + 1) * len; ++k)
	sum += m_nums[k];
	for(int k = startBlock + 1; k < endBlock; ++k)
	sum += m_sq[k];
	for(int k = endBlock * len; k <= j; ++k)
	sum += m_nums[k];
	return sum;
	}
	private:
	int n, len;
	vector<int> m_nums;
	vector<int> m_sq;
	};

view raw Range Sum Query - Mutable_III.cpp hosted with ❤ by GitHub