链接：https://ac.nowcoder.com/acm/problem/23054
来源：牛客网

题目描述

因为上次在月月面前丢人了，所以华华决定开始学信息学。十分钟后，他就开始学树状数组了。这是一道树状数组的入门题：
给定一个长度为N的序列A，所有元素初值为0。接下来有M次操作或询问：
操作：输入格式：1 D K，将AD加上K。
询问：输入格式：2 L R，询问区间和，即。
华华很快就学会了树状数组并通过了这道题。月月也很喜欢树状数组，于是给华华出了一道进阶题：
给定一个长度为N的序列A，所有元素初值为0。接下来有M次操作或询问：
操作：输入格式：1 D K，对于所有满足1≤i≤N且i%D==0的i，将Ai加上K。
询问：输入格式：2 L R，询问区间和，即。
华华是个newbie，怎么可能会这样的题？不过你应该会吧。

输入描述: 

第一行两个正整数N、M表示序列的长度和操作询问的总次数。
接下来M行每行三个正整数，表示一个操作或询问。

输出描述: 

对于每个询问，输出一个非负整数表示答案。

题型：

树状数组--单点修改与区间查询--分块处理思想

思路：

P.S.：这一道题是我做到的第一道关于线段树/树状数组的需要分块处理思想的题目，第一次提交时直接搬模板上去，AC了90%，剩下10%TLE了，然后就一直不知道怎么办，看了题解之后才知道是用分块的思想做，学到了新思想（开心）~
这一道题第一眼看上去就知道是单点修改与区间查询，所以直接先把板子搬上去，再在板子的基础上修修改改
我们可以看出，如果真的按照题目模拟，把D的倍数全部单点修改，那么大概率是会TLE的，就像下面这样（错误代码只展示主要的错误部分） 
scanf("%lld%lld%lld",&op,&x,&y);
if(op==1){
    for(int i=x;i<=n;i+=x){
        add(i,y); //这个地方如果直接这样写，答案是正确的，但是时间复杂度可就高了
    }
}else{
    printf("%lld\n",sum(y)-sum(x-1));
}
为什么会TLE呢？因为当D很小（比如说D=2,N=100000时），相当于要对N/2的点都进行一次单点修改，这样时间复杂度就高了
但是当D大的时候，是可以遍历进行单点修改的，因为遍历的点相对较少
所以，这里就要采用分块的思想，即类似于分类讨论
1.考虑D大的时候，直接暴力枚举每一个点进行单点修改
2.D小的时候，可以增加一个addnum数组，用于记录D的倍数增加的值的大小，这样，在计算[L，R]区间和的时候，里面D的倍数的个数就是(R/D)-((L-1)/D)，注意不能写成(R-(L-1))/D，因为/是整除！
最后，计算区间和的时候，只需要将1和2这两部分加起来，即可得出正确答案

具体看下面代码就行，这道题掌握了分块的思想之后，其实难度属于基础题，重要的是这个思想的掌握

代码： 

#include<bits/stdc++.h>
#define int long long int
using namespace std;
const int N=262145;
int tree[N],addnum[N];
//下面三个函数全是板子
int lowbit(int x) {
	return x&(-x);
}

void add(int i,int val) {
	while(i<=N) {
		tree[i]+=val;
		i+=lowbit(i);
	}
}

int sum(int i) {
	int ans=0;
	while(i>0) {
		ans+=tree[i];
		i-=lowbit(i);
	}
	return ans;
}


signed main() {
	int n,m;
	scanf("%lld%lld",&n,&m);
	while(m--) {
		int op,x,y;
		scanf("%lld%lld%lld",&op,&x,&y);
		if(op==1) { //单点修改（采用分块的思想）
			if(x<=sqrt(n)) {
				addnum[x]+=y;
			} else {
				for(int i=x; i<=n; i+=x) {
					add(i,y);
				}
			}
		} else { //求区间和，两部分相加
			int ans=sum(y)-sum(x-1);
			for(int i=1; i<=sqrt(n); i++) {
				ans+=(y/i-(x-1)/i)*addnum[i];
			}
			printf("%lld\n",ans);
		}
	}
	return 0;
}