题目链接
题目
题目描述
因为上次在月月面前丢人了，所以华华决定开始学信息学。十分钟后，他就开始学树状数组了。这是一道树状数组的入门题：
给定一个长度为 \(N\) 的序列 \(A\) ，所有元素初值为 \(0\) 。接下来有 \(M\) 次操作或询问：
操作：输入格式：1 D K，将 \(A_D\) 加上 \(K\) 。
询问：输入格式：2 L R，询问区间和，即 \(\sum_{i=L}^{R}A_i\) 。
华华很快就学会了树状数组并通过了这道题。月月也很喜欢树状数组，于是给华华出了一道进阶题：
给定一个长度为 \(N\) 的序列 \(A\) ，所有元素初值为 \(0\) 。接下来有 \(M\) 次操作或询问：
操作：输入格式：1 D K，对于所有满足 \(1\le i\le N\) 且 $i\equiv0 \pmod D $ 的 \(i\) ，将 \(A_i\) 加上 \(K\) 。
询问：输入格式：2 L R，询问区间和，即 \(\sum_{i=L}^{R}A_i\) 。
华华是个newbie，怎么可能会这样的题？不过你应该会吧。
输入描述
第一行两个正整数 \(N\) 、\(M\) 表示序列的长度和操作询问的总次数。
接下来M行每行三个正整数，表示一个操作或询问。
输出描述
对于每个询问，输出一个非负整数表示答案。
示例1
输入
10 6
1 1 1
2 4 6
1 3 2
2 5 7
1 6 10
2 1 10
输出
3
5
26
备注
\(1\le N,M\le10^5\) ， \(1\le D\le N\) ， \(1\le L\le R\le N\) ， \(1\le K \le 10^8\)
题解
知识点：树状数组，根号分治。
显然，这道题的修改并不能转化为可懒标记的区间修改，也没有很好的方法转化为单点修改。
我们可以考虑暴力优化的一种，根号分治。将修改操作的 \(D\) 分为两部分，按阈值 \(B\) 划分：
- \(D \leq B\) 时，采用标记法， 用 \(add\) 数组表示某个 \(D\) 加了多少，复杂度 \(O(1)\) 。
\(D > B\) 时，采用暴力修改法，倍增修改树状数组 \(x \equiv 0 \pmod D\) 的点，复杂度 \(O\left( \dfrac{n}{B} \log n \right)\) 。
修改总体复杂度为 \(O\left( \dfrac{n}{B} \log n \right)\) 。
同时，查询操作也要随之改变：
- \(D \leq B\) 部分，暴力累和每个 \(D\) 的贡献，即 \(\displaystyle \sum_{i=1}^B add_i \cdot \left( \left \lfloor \frac{r}{i} \right \rfloor - \left \lfloor \frac{l-1}{i} \right \rfloor \right)\) ，复杂度 \(O(B)\)。
\(D>B\) 部分，直接查询树状数组即可，复杂度 \(O(\log n)\) 。
查询总体复杂度为 \(O(B + \log n)\) 。
我们尝试平衡查询和修改的复杂度。假设 \(B\) 能使 \(\log n\) 被忽略，则需要满足 $ \dfrac{n}{B} \log n = B$ ，解得 \(B = \sqrt{n \log n}\) 。因此， \(B = \sqrt{n \log n}\) 是我们所需要的阈值，其能使总体复杂度为 \(O(\sqrt{n \log n})\) 。
实际上，这道题用理论最优阈值时间不是最优的，用 \(B = \sqrt n\) 快将近一倍，可能由于数据的 \(D\) 普遍较小，使得查询代价上升较明显。
这里采用 \(B = \sqrt n\) 阈值。
时间复杂度 \(O(m\sqrt{n} \log n)\)
空间复杂度 \(O(n)\)
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T>
class Fenwick {
int n;
vector<T> node;
public:
Fenwick(int _n = 0) { init(_n); }
void init(int _n) {
n = _n;
node.assign(n + 1, T::e());
}
void update(int x, T val) { for (int i = x;i <= n;i += i & -i) node[i] += val; }
T query(int x) {
T ans = T::e();
for (int i = x;i >= 1;i -= i & -i) ans += node[i];
return ans;
}
T query(int l, int r) { return query(r) - query(l - 1); }
};
struct T {
ll sum;
static T e() { return { 0 }; }
T &operator+=(const T &x) { return sum += x.sum, *this; }
friend T operator-(const T &a, const T &b) { return { a.sum - b.sum }; }
};
ll add[100007];
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, m;
cin >> n >> m;
Fenwick<T> fw(n);
for (int i = 1;i <= m;i++) {
int op;
cin >> op;
if (op == 1) {
int d, k;
cin >> d >> k;
if (d * d <= n) add[d] += k;
else for (int i = d;i <= n;i += d) fw.update(i, { k });
}
else {
int l, r;
cin >> l >> r;
ll ans = fw.query(l, r).sum;
for (int i = 1;i * i <= n;i++) ans += add[i] * (r / i - (l - 1) / i);
cout << ans << '\n';
}
}
return 0;
}
