这是一道能用许多数据结构优化的经典题，可以用于不同数据结构训练。
数列分块就是把数列中每(m)个元素打包起来，达到优化算法的目的。
以此题为例，如果我们把每(m)个元素分为一块，共有(n/m)块，每次区间加的操作会涉及(O(n/m))个整块，以及区间两侧两个不完整的块中至多(2m)个元素。
我们给每个块设置一个加法标记（就是记录这个块中元素一起加了多少），每次操作对每个整块直接(O(1))标记，而不完整的块由于元素比较少，暴力修改元素的值。
每次询问时返回元素的值加上其所在块的加法标记。
这样每次操作的复杂度是(O(n/m)+O(m))，根据均值不等式，当(m)取(sqrt(n))时总复杂度最低。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=50005;
int a[N],tag[N],L[N],R[N],pos[N];
inline void add(int l,int r,int d) {
int p=pos[l],q=pos[r];
if(p==q) {
for(int i=l; i<=r; i++) {
a[i]+=d;
}
} else {
for(int i=p+1; i<q; i++) {
tag[i]+=d;
}
for(int i=l; i<=R[p]; i++) {
a[i]+=d;
}
for(int i=L[q]; i<=r; i++) {
a[i]+=d;
}
}
}
int main() {
int n;
scanf("%d",&n);
for(int i=1; i<=n; i++) {
scanf("%d",a+i);
}
int t=sqrt(n*1.0);
for(int i=1; i<=t; i++) {
L[i]=(i-1)*t+1,R[i]=i*t;
}
if(R[t]<n) {
t++,L[t]=R[t-1]+1,R[t]=n;
}
for(int i=1; i<=t; i++) {
for(int j=L[i]; j<=R[i]; j++) {
pos[j]=i;
}
}
for(int i=1,opt,l,r,c; i<=n; i++) {
scanf("%d %d %d %d",&opt,&l,&r,&c);
if(!opt) {
add(l,r,c);
} else {
printf("%d
",a[r]+tag[pos[r]]);
}
}
return 0;
}