题目链接

题目

题目描述

因为上次在月月面前丢人了，所以华华决定开始学信息学。十分钟后，他就开始学树状数组了。这是一道树状数组的入门题：

给定一个长度为 (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，对于所有满足 (1le ile N) 且 $iequiv0 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

备注

(1le N,Mle10^5) ， (1le Dle N) ， (1le Lle Rle N) ， (1le K le 10^8)

题解

知识点：树状数组，根号分治。

显然，这道题的修改并不能转化为可懒标记的区间修改，也没有很好的方法转化为单点修改。

我们可以考虑暴力优化的一种，根号分治。将修改操作的 (D) 分为两部分，按阈值 (B) 划分：

1. (D leq B) 时，采用标记法， 用 (add) 数组表示某个 (D) 加了多少，复杂度 (O(1)) 。
2. (D > B) 时，采用暴力修改法，倍增修改树状数组 (x equiv 0 pmod D) 的点，复杂度 (Oleft( dfrac{n}{B} log n right)) 。

修改总体复杂度为 (Oleft( dfrac{n}{B} log n right)) 。

同时，查询操作也要随之改变：

1. (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))。
2. (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(msqrt{n} log n))

空间复杂度 (O(n))

代码

#include 
using namespace std;
using ll = long long;

template
class Fenwick {
    int n;
    vector 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 = 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 fw(n);
    for (int i = 1;i > op;
        if (op == 1) {
            int d, k;
            cin >> d >> k;
            if (d * d > l >> r;
            ll ans = fw.query(l, r).sum;
            for (int i = 1;i * i 

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.e1idc.net