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{block\_size}=\lceil \sqrt{N} \rceil$. 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{block\_size}}$.

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{block\_size},(i + 1)\cdot \texttt{block\_size})$, and $R=\left\lceil \frac{r}{\texttt{block\_size}} \right\rceil$.

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
#include <bits/stdc++.h>
using namespace std;

struct Sqrt {
	int block_size;
	vector<int> nums;
	vector<long long> blocks;
	Sqrt(int sqrtn, vector<int> &arr) : block_size(sqrtn), blocks(sqrtn, 0) {
		nums = arr;
		for (int i = 0; i < nums.size(); i++) { blocks[i / block_size] += nums[i]; }

Copy
import java.io.*;
import java.util.*;

public class DRSQ {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(System.out);
		StringTokenizer st = new StringTokenizer(br.readLine());

		int n = Integer.parseInt(st.nextToken());

Combining Algorithms

Doing this problem with DP has a time complexity of $\mathcal{O}(N^2)$.

Copy
vector<int> dp(n, 1);
for (int i = n - 1; i >= 0; i--) {
	for (int x = i + a[i]; x <= n; x += a[i]) { dp[i] = (dp[i] + dp[x]) % MOD; }
}

If we try prefix sums, the complexity is still $\mathcal{O}(N^2)$.

Copy
for (int i = n - 1; i >= 0; i--) {
	dp[i] += s[a[i]][i % a[i]];
	dp[i] %= MOD;

	for (int j = 1; j <= x; j++) {
		s[j][i % j] += dp[i];
		s[j][i % j] %= MOD;
	}
}

We can apply the DP algorithm to the steps where $A_i \cdot x >= \sqrt(N)$ because the jump is bigger, thus resulting in a faster loop We can apply prefix sums for the remaining cases where $A_i \cdot x < \sqrt(N)$.

This trick allows us to combine two $\mathcal{O}(N^2)$ algorithm into one $\mathcal{O}(N\sqrt(N))$ algorithm.

Copy
#include <bits/stdc++.h>
using namespace std;

const int MOD = 998244353;

int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) { cin >> a[i]; }

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
#include <bits/stdc++.h>
using namespace std;

int n, q;
vector<int> arr;
vector<long long> prefix;

/** Build the prefix array for arr */
void build() {
	prefix[0] = 0;

Copy
import java.io.*;
import java.util.*;

public class DRSQ {
	static int[] arr;
	static List<Long> prefix;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(System.out);

Mo's Algorithm

Copy
#include <bits/stdc++.h>
using namespace std;

struct Query {
	int l, r, idx;
};

int main() {
	int n;
	cin >> n;

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!