[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))，代码如下：