Square Root Decomposition

You should already have done this problem in Point Update Range Sum, but here we'll present two more approaches. Both run in $\mathcal{O}(Q\sqrt N)$ time.

Blocking

We partition the array into blocks of size $\texttt{blocksz}=\lfloor \sqrt{N} \rfloor$. Each block stores the sum of elements within it, and allows for the creation of corresponding update and query operations.

Update Queries: $\mathcal{O}(1)$

To update an element at location $x$, first find the corresponding block using the formula $\frac{x}{\texttt{blocksz}}$.

Then, apply the corresponding difference between the element currently stored at $x$ and the element we want to change it to.

Sum Queries: $\mathcal{O}(\sqrt{N})$

To perform a sum query from $[0\ldots r]$, calculate

where $\texttt{blocks}[i]$ represents the total sum of the $i$-th block, the $i$-th block represents the sum of the elements from the range $[i\cdot \texttt{blocksz},(i + 1)\cdot \texttt{blocksz})$, and $R=\left\lfloor \frac{r}{\texttt{blocksz}} \right\rfloor$.

Finally, $\sum_{i=l}^{r} \texttt{nums}[i]$ is the difference between the two sums $\sum_{i=0}^{r}\texttt{nums}[i]$ and $\sum_{i=0}^{l-1}\texttt{nums}[i]$, which each are calculated in $\mathcal{O}(\sqrt N)$.

Copy
 Code Snippet: C++ Short Template (Click to expand)

ll blocks[450]; // 450^2 > 2e5
int nums[(int)(2e5 + 1)];
int block_sz;

void upd(int x, int v) { // O(1) update
	blocks[x / block_sz] -= nums[x];
	nums[x] = v;
	blocks[x / block_sz] += nums[x];

Batching

See the CPH section on batch processing.

Maintain a "buffer" of the latest updates (up to $\sqrt N$). The answer for each sum query can be calculated with prefix sums and by examining each update within the buffer. When the buffer gets too large ($\ge \sqrt N$), clear it and recalculate prefix sums.

Copy
 Code Snippet: C++ Short Template (Click to expand)

int n, q;
vi x;
vector<long long> cum;

void build() {
	cum = {0};
	for(const auto &t : x) cum.pb(cum.back() + t);
}

Mo's Algorithm

Additional Notes

• Low constraints (ex. $n=5\cdot 10^4$) and/or high time limits (greater than 2s) can be signs that square root decomposition is intended.

• CPH 262:

• In practice, it is not necessary to use the exact value of $\sqrt n$ as a parameter, and instead we may use parameters $k$ and $n/k$ where $k$ is different from $\sqrt n$. The optimal parameter depends on the problem and input. For example, if an algorithm often goes through the blocks but rarely inspects single elements inside the blocks, it may be a good idea to divide the array into $k<\sqrt n$ blocks, each of which contains $n/k > \sqrt n$ elements.

• If an update takes time proportional to the size of one block ($\mathcal{O}(n/k)$) while a query takes time proportional to the number of blocks times $\log n$ ($\mathcal{O}(k\log n)$) then we can set $k\approx \sqrt{\frac{n}{\log n}}$ to make both updates and queries take time $\mathcal{O}(\sqrt{n\log n})$.

• Solutions with worse complexities are not necessarily slower (at least for problems with reasonable input sizes, ex. $n\le 5\cdot 10^5$). I recall an instance where a fast $\mathcal{O}(n\sqrt n\log n)$ solution passed (where $\log n$ came from a BIT) while an $\mathcal{O}(n\sqrt n)$ solution did not. Constant factors are important!

On Trees

The techniques mentioned in the blogs below are extremely rare but worth a mention.

Some more discussion about how square root decomposition can be used:

Problems

Set A

Problems where the best solution involves square root decomposition.

Set B

Problems that can be solved without it. But you might as well try to use it!