wiki - 算法小站

主题名称

是否为父主题

是否为其添加wiki文章

选择主题

修改主题名称

修改父主题

修改wiki文章

算法基础搜索数据结构字符串数学图论动态规划计算几何杂项

数据结构

线段树

线段树单点修改

线段树区间修改

动态开点线段树

线段树的合并（一）

可持久化线段树

树链剖分

平衡树

FHQ-Treap

珂朵莉树

分块

位分块

根号分治

[[ item.c ]]

根号分治

## 根号分治
算法思想，按照$$B$$来分块，$$\leqslant B$$的直接暴力，$$> B$$的**整体维护**

###  2025“钉耙编程”算法设计暑期联赛（10）
#### 1002
**[Multiple and Factor](https://acm.hdu.edu.cn/contest/problem?cid=1181&pid=1002)**
给定一个长度为$$n$$的序列`a`，支持以下操作
```bash
1 x k，给下标是 x 倍数的位置上的值 +k
2 x k，给下标是 x 因子的位置上的值 +k
3 x，查询下标是 x 倍数的位置上的值的和
4 x，查询下标是 x 因子的位置上的值的和
```

**算法分析**
可以设置一个块长，不妨设为$$B$$，$$x > B$$的部分，此时$$x$$的倍数就不是很多了
可以暴力修改，$$\leqslant B$$的部分，整体维护

具体来说，对于$$> B$$的修改，我们直接修改`a[x 的倍数]`，而对于$$\leqslant B$$的修改呢？
维护两个值，一个是标记`add[x]`，表示**所有**$$x$$的倍数，应该要增加多少？
这个时候不能直接`for y = x 的倍数了`，而是把它们的和整体维护起来，用`sum[x]`表示`x 的倍数的和`

> 对于修改`1 x k`

如果$$x > B$$，那么首先暴力修改`for y = x 的倍数`，`a[y] += k`
另一方面，如果$$x$$存在$$\leqslant B$$的因子$$d$$，那么$$x$$的修改会影响到$$d$$
`sum[d] += K * (d 的倍数中，也是 x 的倍数有多少个？)`，$$sum(d) += \lfloor \dfrac{n}{lcm(d, x)} \rfloor$$

> 对于修改`2 x k`

因为$$x$$的因子最多$$O(\sqrt{n})$$个，可以暴力更改`for d = x 的因子`
只是，对于$$d \leqslant B$$，需要同步维护$$sum(d)$$
`sum[d] += K * (d 的倍数中，是 x 的因子有多少个？)`，$$sum[d] += K \cdot |fac(\lfloor \dfrac{x}{d} \rfloor)|$$
其中$$|fac()|$$表示因子的个数

这部分的原理是`d * [... ? ...] = x`，`x`的增加`k`，`d`不止会增加`k`
`d * ([... ? ...] 的因子)`都会`+k`，所以`(d, 2d, 3d, ...)`一起放到$$d$$来结算，`sum[d] += cnt(x/d) * K`

> 对于查询`3 x`

如果$$x > B$$，那么首先基础的部分，`for x 的倍数 y，ans += a[y]`
除此之外，还应该把标记的影响加上，考虑`for d = 1 to B`的每个标记`add(d)`
`ans += (d 的倍数中，同时也是 x 的倍数的个数) * add(d)`，$$ans += add(d) \cdot \lfloor \dfrac{n}{lcm(d, x)} \rfloor$$

如果$$x \leqslant B$$，那么基础的部分`ans += sum[x]`，同样还要加上其他标记的贡献
即，$$\forall d \in [1, B], \quad ans += add(d) \cdot \lfloor \dfrac{n}{lcm(d, x)} \rfloor$$

> 对于查询`4 x`

关于$$x$$的因子，可以暴力，把`ans += a[x 的因子 d]`，注意到如果$$d \leqslant B$$
这个时候我们只加了基础的`a[d]`，即**未经修改**的`a[d]`，还需要补上修改的部分
修改的部分我们考虑`add[...]`

考虑`for j = 1 to B`，`ans += add[j] * (j 的倍数中，是 x 的因子的有多少个？)`
那么答案就是`if (add[j] and x % j == 0) ans += add[j] * sz[ x/j ]`

#### 算法实现
```bash
int B = 400;

void solve(int cas) {
    int n, m;
    cin >> n >> m;

B = min(B, (int)sqrt(n));

auto LCM = [&](i64 x, i64 y) -> i64 {
        return x * y / std::gcd(x, y);
    };

vector<i64> a(n+1, 0);
    for (int i = 1; i <= n; i++) cin >> a[i];

vector<vector<int> > facs(n+1);
    for (int x = 1; x <= n; x++) {
        for (int y = x; y <= n; y += x) facs[y].emplace_back(x);
    }

vector<int> sz(n+1, 0);
    for (int x = 1; x <= n; x++) sz[x] = facs[x].size();

vector<i64> add(n+1, 0), msum(n+1, 0);
    for (int x = 1; x <= B; x++) {
        for (int y = x; y <= n; y += x) msum[x] += a[y];
    }

for (int i = 0; i < m; i++) {
        int op;
        cin >> op;

if (op == 1) {
            int x;
            i64 K;
            cin >> x >> K;

if (x <= B) add[x] += K;
            else {
                for (auto y = x; y <= n; y += x) a[y] += K;

for (int d = 1; d <= B; d++) {
                    auto lcm = LCM(1LL * d, 1LL * x);
                    if (lcm > n) continue;

i64 c = n / lcm;
                    msum[d] += 1LL * c * K;
                }
            }

}
        else if (op == 2) {
            int x;
            i64 K;
            cin >> x >> K;

for (int d = 1; d <= B; d++) if (x % d == 0) {
                msum[d] += 1LL * K * sz[x / d];
            }

for (auto d : facs[x]) a[d] += K;
        }
        else if (op == 3) {
            int x;
            cin >> x;

i64 ans = 0;
            if (x <= B) ans += msum[x];
            else {
                for (auto y = x; y <= n; y += x) ans += a[y];
            }

for (int d = 1; d <= B; d++) if (add[d]) {
                auto lcm = LCM(1LL * d, 1LL * x);
                if (lcm > n) continue;

i64 c = n / lcm;
                ans += c * add[d];
            }

cout << ans << "\n";
        }
        else {
            int x;
            cin >> x;

i64 ans = 0;
            for (auto d : facs[x]) ans += a[d];
            for (int d = 1; d <= B; d++) if (add[d]) {
                if (x % d) continue;

ans += 1LL * add[d] * sz[x / d];
            }

cout << ans << "\n";
        }
    }
}
```

> 这个问题的核心

实际上，对于因子操作，因为只有$$\sqrt{n}$$个因子，可以枚举所有因子$$d$$，暴力地$$a[d] += K$$

而对于倍数操作，如果$$x$$很小，那么倍数很多，枚举是不现实的
```bash
x 的倍数都加上一个值，用懒标记 tag[x] += d 维护
x 的所有倍数的和，用 msum[x] 来维护
```

查询和修改的时候，注意对$$x \in [1, B]$$，`tag[x]`和`msum[x]`的影响即可

**另外**，这个问题中，对于$$x \leqslant B$$，`x`的倍数的和不用直接求了，`msum[x]`直接维护
而$$x$$的因子，仍然可以暴力修改

对于$$x \leqslant B$$的所有修改操作，**已经发生但尚未修改的**，都放在$$add(x)$$中

> 总结

因子的修改直接在`a[x]`上改，不需要标记，只是`msum[x]`关于倍数求和的答案需要实时维护
而倍数的修改，$$x \leqslant B$$需要标记，把$$x$$的倍数都`+ K`

看完文章有啥想法

算法小站

wiki 主题

数据结构

根号分治

目录