华华开始学信息学

当d<=sqrt(n)时 直接暴力修改树状数组的值会使复杂度退化到O(n²)
所以这里要用到分块的思想，修改lazy标记
lazy[i]表示i的倍数的位置中所有的数组成的一个块，查询时l到r对应的lazy，这中间有r/i-(l-1)/i个数，乘以lazy[i]就是分块记录的答案
跟树状数组直接记录的答案相加就是最终的答案

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
const int N=100010;
int c[N];
int lazy[1000];
int lowbit(int x)
{
    return x&(-x);
}
void update(int x,int k)
{
    while(x<=n)
    {
        c[x]+=k;
        x+=lowbit(x);
    }
}
int getsum(int x)
{
    int ans=0;
    while(x>=1)
    {
        ans+=c[x];
        x-=lowbit(x);
    }
    return ans;
}
signed main()
{
    scanf("%lld%lld",&n,&m);
    while(m--)
    {
        int op;
        scanf("%lld",&op);
        if(op==1)
        {
            int d,k;
            scanf("%lld%lld",&d,&k);
            if(d<=sqrt(n))
            {
                lazy[d]+=k;
            }
            else
            {
                for(int i=d;i<=n;i+=d)
                {
                    update(i,k);
                }
            }
        }
        else
        {
            int l,r;
            scanf("%lld%lld",&l,&r);
            int ans=getsum(r)-getsum(l-1);
            for(int i=1;i<=sqrt(n);i++)
                ans+=((r/i)-(l-1)/i)*lazy[i];
            printf("%lld\n",ans);
        }
    }
}