可能涉及的几个词语解释:
区间:数列中连续一段的元素
区间操作:将某个区间[a,b]的所有元素进行某种改动的操作
块:我们将数列划分成若干个不相交的区间,每个区间称为一个块
整块:在一个区间操作时,完整包含于区间的块
不完整的块:在一个区间操作时,只有部分包含于区间的块,即区间左右端点所在的两个块
数列分块入门1
把每m个元素分为一块,共有 $n/m$ 块,每次区间加的操作会涉及 $O(n/m)$ 个整块,以及区间两侧两个不完整的块中至多 $2m$ 个元素。
我们给每个块设置一个加法标记(就是记录这个块中元素一起加了多少),每次操作对每个整块直接O(1)标记,而不完整的块由于元素比较少,暴力修改元素的值。
每次询问时返回元素的值加上其所在块的加法标记。
这样每次操作的复杂度是 $O(n/m)+O(m)$ ,根据均值不等式,当m取 $ \sqrt n $ 时总复杂度最低,为了方便,我们都默认下文的分块大小为 $\sqrt n$。
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=5e4+10;
int v[N],bl[N],atag[N];//v存储数据,bl存储i属于那个块,atag存储该块整体要加的值
int n,blo;
void add(int a,int b,int c){
for(int i=a;i<=min(bl[a]*blo,b);i++){//如果都在一个块,把a所在块暴力加上
v[i]+=c;
}
if(bl[a]!=bl[b]){//如果不在一个块,把b所在块暴力加上
for(int i=(bl[b]-1)*blo+1;i<=b;i++){
v[i]+=c;
}
}
for(int i=bl[a]+1;i<=bl[b]-1;i++){//把a,b中间块用atag做标记
atag[i]+=c;
}
}
int main(){
scanf("%d",&n);
blo=sqrt(n);
for(int i=1;i<=n;i++) scanf("%d",&v[i]);//因为题目是从1开始数的
for(int i=1;i<=n;i++) bl[i]=(i-1)/blo+1;//计算一下i属于那个块
while(n--){
int f,a,b,c;
scanf("%d%d%d%d",&f,&a,&b,&c);
if(f==0) add(a,b,c);
if(f==1) printf("%d\n",v[b]+atag[bl[b]]);//记得要加上atag的值
}
return 0;
}