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}((N+Q)\sqrt{N})$ time.

Blocking

See the first example in CPH.

1int n,q;
2vi x;
3ll block[450];
4int BLOCK;
5
6ll sum(int a) { // sum of first a elements of array in O(sqrt(n)) time
7    ll ans = 0;
8    F0R(i,a/BLOCK) ans += block[i];
9    FOR(i,a/BLOCK*BLOCK,a) ans += x[i];
10    return ans;

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.

1int n,q;
2vi x;
3vl cum;
4
5void build() {
6    cum = {0};
7    trav(t,x) cum.pb(cum.bk+t);
8}
9
10int main() {

Mo's Algorithm

See CPH 27.3 and the CF link above.

Additional Notes

Low constraints (ex. $n=5\cdot 10^4$) and/or high time limits (greater than 2s) can be signs that sqrt decomp 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.

As another example, 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 ... So 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 sqrt decomp can be used:

Problems

A

Problems where the best solution I know of involves sqrt decomp.

B

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