在这里插入图片描述
思路：
分块，树状数组
直接树状数组进行add操作
for(int i=d;i<=n;i+=d))add(d,k)
时间复杂度起码是O(n^m^)=1e10，肯定t
这个时候我们可以考虑进行分块操作
对于d小于等于√n的我们就存到一个lazy数组里
大于√n的我们就直接进行树状数组的add操作
这样的话根据上面那个循环我们add操作时间复杂度差不多是log^2^(n)(树状数组本身add操作为logn)
而lazy操作为O1
查询区间和的时候
lazy操作为logn（直接扫一遍下标小于logn的数)
得树状数组和也为logn
这样就能大大优化时间复杂度得到答案了

AC代码：

#include <iostream>
#include <math.h>
#define IOS ios::sync_with_stdio(false);
using namespace std;
typedef long long ll;
const int N=1e5+10;
ll a[N];
ll lazy[N];
ll c[N];
int n,m;
int lower_bit(int x)
{
    return x&(-x);
}
ll getsum(int x)
{
    ll cnt=0;
    while(x>0)
    {
        cnt+=c[x];
        x-=lower_bit(x);
    }
    return cnt;
}
void add(int x,ll k)
{
    while(x<=n)
    {
        c[x]+=k;
        x+=lower_bit(x);
    }
    return;
}
int main()
{
    IOS;
    cin>>n>>m;
    while(m--)
    {
        int q;
        cin>>q;
        if(q==1)
        {
            int d,k;
            cin>>d>>k;
            if(d<=sqrt(n))
            {
                lazy[d]+=k;
            }
            else
            {
                for(int i=1; i*d<=n; i++) //logn时间复杂度
                {
                    add(d*i,k);
                }
            }
        }
        else
        {
            int l,r;
            cin>>l>>r;
            ll ans=getsum(r)-getsum(l-1);
            for(int i=1; i<=sqrt(n); i++) //logn时间复杂度
            {
                ans+=(r/i-(l-1)/i)*lazy[i];
            }
            cout<<ans<<endl;
        }
    }
    return 0;
}