题目
题目描述
给定一个长度为 \(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，怎么可能会这样的题？不过你应该会吧。
输入描述
接下来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
备注
题解
知识点：树状数组，根号分治。
我们可以考虑暴力优化的一种，根号分治。将修改操作的 \(D\ 分为两部分，按阈值 \(B\ 划分：
-
\(D \leq B\ 时，采用标记法，用 \(add\ 数组表示某个 \(D\ 加了多少，复杂度 \(O(1\ 。
- \(D > B\ 时，采用暴力修改法，倍增修改树状数组 \(x \equiv 0 \pmod D\ 的点，复杂度 \(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\ 。
我们尝试平衡查询和修改的复杂度。假设 \(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\ 阈值。
空间复杂度 \(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;
}