写在前面
非常简单的分块，使我开心的转圈，稍微看了一下 oi wiki 就懂了，妈妈再也不用担心我的暴力了
正文
分块，非常优雅的暴力，本质是上是通过对原数据的适当划分，并在划分后的每一个块上预处理部分信息，从而较一般的暴力算法取得更优的时间复杂度。
例如（博客萌新好不容易整的）：
\(n\) 如果不是s的倍数最后一个块可能不完整，但也没关系，对最后操作无影响
查询操作
如果负责查询的 \(l,r\) 都在同一个块中，暴力枚举 \(l\) 到 \(r\)
如果 \(l\) 或 \(r\) 不在所在块的头或尾，则暴力将 \(l\) 和 \(r\) 枚举到块的头或尾部
然后再从 \(l\) 所在的整块枚举整快到 \(r\) 所在的整块，将所有查询结果加和，即为结果
修改操作
和查询操作的思路一样
就是在整块修改时，无法依次修改块中元素，需要在修改时打个 \(add[]\) 标记，存储整块 \(k[]\) 的值被修改了，而单点 \(a[]\) 却没有被修改的数值，在查询单点 \(a[]\) 时加上标记就行
警示后人
在判断第 \(i\) 个数属于哪个块时，要注意对于任意一个块 \(k[j]\) （为了简单举 \(j=1\) 的例子）的下标为 \(1,2,3 \cdots,s\)
然而 \(1,2,3 \cdots,s-1\) 的下标 \(i\) 进行对应块的下标却为 \(\tfrac{i}{s}+1\) ，要记得特判
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int a[N],k[N],add[N];
int n,s,cnt,m,op,u,v,ad;
int id(int x){
if(x%s==0) return x/s;
return x/s+1;
}
void change(int x,int y,int ad){
if((id(x))==(id(y))){
for(int i=x;i<=y;i++){
a[i]+=ad;
}
k[id(x)]+=ad*(y-x+1);
return;
}
while(x%s!=1){
a[x]+=ad;
k[id(x)]+=ad;
x++;
}
while(y%s!=0){
a[y]+=ad;
k[id(y)]+=ad;
y--;
}
for(int i=id(x);i<=id(y);i++){
k[i]+=ad*s;
add[i]+=ad;
}
}
int query(int x,int y){
int res=0;
if(id(x)==id(y)){
for(int i=x;i<=y;i++){
res+=a[i]+add[id(i)];
}
return res;
}
// printf("nsbsbnsbs\n");
while(x%s!=1){
// printf("x=%d\n",x);
res+=a[x]+add[id(x)];
x++;
// printf("res=%d\n",res);
}
while(y%s!=0){
// printf("y=%d\n",y);
res+=a[y]+add[id(y)];
y--;
// printf("res=%d\n",res);
}
// printf("x=%d y=%d\n",x,y);
for(int i=id(x);i<=id(y);i++){
res+=k[i];
// printf("res=%d\n",res);
}
return res;
}
signed main(){
scanf("%lld%lld",&n,&m);
s=(int)sqrt(n);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
if(i%s==1){
cnt++;
}
k[cnt]+=a[i];
}
// for(int i=1;i<=cnt;i++){
// printf("%d ",k[i]);
// }
// printf("\nlll\n");
for(int i=1;i<=m;i++){
scanf("%lld%lld%lld",&op,&u,&v);
if(op==1){
scanf("%lld",&ad);
change(u,v,ad);
}
else{
printf("%lld\n",query(u,v));
}
}
}