用来处理一些根号范围以内复杂度高（打表），根号范围以外复杂度低（枚举）的一种暴力思想，一般能做到$O(n\sqrt n)$的复杂度，大多数都是多组数据询问。

P3396 哈希冲突

一个长度为n 的序列和m个操作，每次操作可以以下二选一：
1 询问下标模x后为y的所有数之和
2 修改第x个数
n≤150000，m≤150000，元素范围是[1,1000]的整数
暴力做法是直接枚举，比如模2后为1的有1,3,5,7…，模10后为1的有11,21,31,41,51…可以发现对于长度为n的，模x后为y的数大概有$\left \lfloor \frac{n}{x} \right \rfloor$个，当x越大那么这个数越小，所以模数越大的可以考虑直接暴力枚举而不会超时，那么问题在于如何处理模数小的询问，当模数小的时候因为余数的范围变小了所以考虑直接先打表预处理出所有的情况，令sum[i][j]表示n个数中下标模i后为j的所有的数的总和，那么可以在O(np)的复杂度内预处理出所有情况，其中p为指定的最大的模数，同时修改也很简单，单次修改的复杂度是O(p)：

1
2
3
4
5
6
7
// 预处理
for (int j = 1; j <= n; ++j)
    for (int i = 1; i <= p; ++i)
        sum[i][j % i] += a[j];
// 修改
for (int i = 1; i <= p; ++i) sum[i][x % i] += y - a[x];
a[x] = y;

所以在模数小于p的情况下直接O(1)查询，模数大于p的情况下最坏大概是$O(\left \lfloor m\frac{n}{p} \right \rfloor )$计算，并且预处理和修改的最坏情况（全是修改）下复杂度都是O(np)，后两者的复杂度是较高的，那么由均值定理得当他们两个相等的时候总体的复杂度是最低的即$m\frac{n}{p} = n\frac{n}{p} = np$,得$p = \sqrt n$,此时是最小的,所以p大概取390左右。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
const int p = 390;

int n, a[N];
int sum[p+1][p+1];

void init() {
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int j = 1; j <= n; ++j) 
        for (int i = 1; i <= p; ++i)
            sum[i][j % i] += a[j];
}

void solve() {
    char cmd;
    int x, y;
    cin >> cmd >> x >> y;
    if (cmd == 'A') {
        int ans = 0;
        if (x > p) for (int i = y; i <= n; i += x) ans += a[i];
        else ans = sum[x][y];
        cout << ans << endl;
    } else {
        for (int i = 1; i <= p; ++i) sum[i][x % i] += y - a[x];
        a[x] = y;
    }
}

Sum of Progression

给你一个长度为 $n$ 的数列 $a$。有 $q$ 次询问，每次询问给出 $s,d,k$，你需要回答 $\displaystyle\sum_{i=1}^ka_{s+(i-1)d}\times i$ 的值。
$s,d,k\leq n\leq 10^5,q\leq 2\times 10^5,s+d(k-1)\leq n,|a_i|\leq 10^8$。
看出这是等差数列，可以发现d越大增长的越快p的取值与上一题的证明类似，都是对形如一次函数和反比例函数之和求最小值，这道题p大概可以取320。
预处理要比上一道要复杂些，这里用后缀和处理更简单一些。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
const int p = 320;

int n, q, s, d, k, a[N];
int sum[N + p][p + 5], f[N + p][p + 5];

void init() {
	cin >> n >> q;
	for(int i=1;i<=n+p;i++) 
		for(int j=1;j<=p;j++) 
			sum[i][j]=0,f[i][j]=0;	
	for (int i = 1; i <= n; ++i) cin >> a[i];
	for (int i = 1; i <= p; ++i) {
		for (int j = n; j >= 1; j--)
			sum[j][i] = sum[j + i][i] + a[j],
			f[j][i] = f[j + i][i] + sum[j + i][i] + a[j];
	}
}

void solve() {
	while (q--) {
		cin >> s >> d >> k;
		if (d <= p) {
			int last = s + d * k;
			if (last > n)cout << f[s][d] << ' ';
			else cout << f[s][d] - f[last][d] - sum[last][d]*k << ' ';
		} else {
			int ans = 0, cnt = 1;
			for (int i = s; i <= s+d*(k-1); i += d)
				ans += a[i] * cnt, cnt++;
			cout << ans << ' ';
		}
	}
	cout << endl;
}

根号分治只是一种思想，只要是对于一次循环内的复杂度呈单调增或单调减都可以用这种思想，并且不一定是在根号处划分枚举与打表的界限，具体怎么判断要对复杂度分析后才可以。