这篇文章上次修改于 447 天前，可能其部分内容已经发生变化，如有疑问可询问作者。

算法学习笔记(7): 根号分治

根号分治是一种对暴力的优化，类似于一种优雅的暴力。

对于一个问题的解决，我们可能有多种暴力的思路，但对于暴力思路A来说，空间占用过大。对于暴力思路B来说，时间占用过大。

两个暴力思路各有自己的优点。这里举出题目例子更好理解。

P3396 哈希冲突

题目大意：给出一个数组arr，有多次查询，每次询问有两个值，m和k，问下标模m余k的所有元素之和。

对于这个题目要求，有两个暴力思路

思路A

如果只有一次查询，我们的暴力思路就是

int result = 0;
for(int i = k; i < n; i += m)
    result += arr[i];

但实际有多次查询，这种查询十分消耗时间，m越小，需要添加的次数就越多

为了减少这种多次查询的高时间复杂度，可以采用空间换时间的思路

思路B

使用一个二维数组保存查询结果

cin >> a[i];
for(int m = 1; m< n; m++)
    res[m][i % m] += a[i];

其中res[m][k]就代表了以m为除数，余数为k的数的总和。

但是我们可以发现，res的大小是n * n，一旦n比较大，将会使用大量的空间，并且有一半的空间都属于空的没有用的状态，消耗了很多空间。但查询成功做到了O(1)

分析

对两个思路进行分析，分析其优缺点。

思路A可以对大的m进行高效查找并且节约空间

思路B可以对小的m进行高效缓存并且节约时间

为此，不妨进行一个结合，如果找到一个分界点，让小的m使用思路B，让大的m使用思路A，就可以兼得两者的优点，达到空间和时间的平衡，对于这个思路，有一个结论就是，分界点取根号N的常数倍。

这个思路就是根号分治

题解代码

#include <bits/stdc++.h>

using namespace std;

int ans[501][501];

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

    vector<int> arr(n + 1);
    // vector<vector<int>> ans(n + 2, vector<int>(n + 2));

    int line = sqrt(n);

    for (int i = 1; i <= n; i++)
    {
        cin >> arr[i];
        for (int p = 1; p <= line; p++)
            ans[p][i % p] += arr[i];
    }
    while (m--)
    {
        int x, y;
        char op;
        cin >> op >> x >> y;
        if ('A' == op)
        {
            if (x <= line)
                cout << ans[x][y] << endl;
            else
            {
                int sum = 0;
                for (int i = y; i <= n; i += x)
                    sum += arr[i];
                cout << sum << endl;
            }
        }
        else
        {
            for (int p = 1; p <= line; p++)
            {
                ans[p][x % p] -= (arr[x] - y);
            }
            arr[x] = y;
        }
    }
}

这种算法的时间复杂度是O(N根号N)

根号分治适用于这种多查询的问题，其中对于查询来说，还有密度问题，前密后疏适合使用

对于分界点，分界点越小，时间越大空间越小。分界点越大，时间越小空间越大

练习可见codeforces920 F题，题型一致

Mai Icy