根号

一. 根号分治

精髓就是拼接两个暴力

1. 余数根号分治：Remainder Problem

首先直接单点更新O(1)，查询暴力跳O(n)。这个暴力的有点在于当查询的x比较大的时候，那么跳的次数就比较少。
另一种暴力思路就是维护c[i][j]为%i = j的下标的数的和，那么更新就是O(n)的，查询则变成O(1)的了。
我们考虑分治 设阈值为B。
当x<=B时用暴力2 O(B) O(1)
x > B时用暴力1 O(1) O(n/B)
B = sqrt(n)时 B = n / B

if(op == 1)
{rep(i, 1, B) c[i][x % i] += y;a[x] += y;
}
else
{if(x <= B) cout << c[x][y] << '\n';else{int res = 0;for(int i = y; i <= 500000; i += x) res += a[i];cout << res << '\n';}
}

小变化

给定一个长度为 ( n ) 的序列 ( x )（元素编号从 ( 1 ) 开始），所有元素初始值为 ( 0 )。接下来进行 ( q ) 次操作，每次操作分为以下两种类型（操作含参数 ( a, b )）：

设有长度为 n 的序列 \(x = (x_1, x_2, \dots, x_n)\)，初始时满足全0

接下来进行 q 次操作，每次操作分为以下两类之一：

1. 更新操作：给定 a, b，对所有满足 \(a \cdot i \le n\) 的正整数 \(i\)，执行
   \(x_{a \cdot i} \leftarrow x_{a \cdot i} + b\).

2. 查询操作：给定 \(a, b \; (a \le b)\)，输出
   \(\sum_{i=a}^{b} x_i\).
   暴力1，直接跳着修改然后BIT查询，复杂度\(O(log(n) \times \sqrt{n})\)
   暴力2，对于每个修改直接记录tag[a]加了多少，查询时在区间内查看a的倍数有几个在区间内即为贡献 \(O(B)\)
   然后就可以对于a<=B用2，a>B用