分块、树状数组

题意：

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

华华很快就学会了树状数组并通过了这道题。月月也很喜欢树状数组，于是给华华出了一道进阶题：
给定一个长度为N的序列A，所有元素初值为0。接下来有M次操作或询问：
操作：输入格式：1 D K，对于所有满足i≡0(modD)的i，将加上K。
询问：输入格式：2 L R，询问区间和，即sum(L,R)
华华是个newbie，怎么可能会这样的题？不过你应该会吧。
输入描述:
第一行两个正整数N、M表示序列的长度和操作询问的总次数。
接下来M行每行三个正整数，表示一个操作或询问。
输出描述:
对于每个询问，输出一个非负整数表示答案。

分析：

这题让我接触到了分块的思想，虽然很简单却很好。该说不愧是雨神挑选出来的题吗。似乎在多校第一场有一道题就有分块的思想，好像是分度数大的节点，和度数小的节点。当时就没做出来。现在看看这道题真的很有启发意义。

我们倘若直接用树状数组加的话，如果D过小比如1那么我们足足要加n次，时间复杂度爆炸。
那如果我们把每次要相加的记录下来lazy[D]+=K那么在我们计算和时

for (int i=1;i<=n;i++)
    ans+=(b/i - (a-1)/i)=lazy[i]

同样时间复杂度爆炸。

我们发现对于D过小时树状数组吃不消，D过大时lazy[]吃不消
那么分块的想法就出来了。
对于D<=sqrt(n)时我们使用lazy[]记录一下
对于D>sqrt(n)时我们用树状数组直接加上
在最后计算和时我们先用树状数组计算一下，然后再用lazy

for (int i=1;i<=sqrt(n);i++)
    ans+=(b/i - (a-1)/i)=lazy[i]

如此操作时间复杂度便大大减小了！！！！！！！简单而神奇。

代码如下：

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int max_n = 1e5 + 100;
const int max_sq = 1e3;
int n, m;
ll BIT[max_n];
ll sq[max_sq];

void renew(int id,int val) {
    for (;id <= n;id += (id & -id))BIT[id] += val;
}

ll quiry(int id) {
    if (id == 0)return 0;
    ll res = 0;
    for (;id;id -= (id & -id))res += BIT[id];
    return res;
}

int main() {
    ios::sync_with_stdio(0);
    cin >> n >> m;
    for (int i = 1;i <= m;i++) {
        int type;int x, y;
        cin >> type >> x >> y;
        if (type == 1) {
            if (x <= sqrt(n))sq[x] += y;
            else {
                for (int i = 1;i * x <= n;i++)
                    renew(i * x, y);
            }
        }
        else {
            ll ans = quiry(y) - quiry(x - 1);
            for (int i = 1;i <= sqrt(n);i++)
                ans += (y / i - (x - 1) / i) * sq[i];
            cout << ans << endl;
        }
    }
}