分块
陈子骏
2018-10-18 15:27:12
```
#include<bits/stdc++.h>
using namespace std;
const int N=5e4+1e3;
int n,k;
int a[N],b[N],lt[N];
void add(int l,int r,int c){
for(int i=l;i<=min(r,b[l]*k);i++) a[i]+=c;
if(b[l]!=b[r])
for(int i=(b[r]-1)*k+1;i<=r;i++) a[i]+=c;
for(int i=b[l]+1;i<=b[r]-1;i++) lt[i]+=c;
}
int val(int x){
return a[x]+lt[b[x]];
}
int main(){
scanf("%d",&n);
k=sqrt(n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=(i-1)/k+1;
for(int i=1,opt,l,r,c;i<=n;i++){
scanf("%d%d%d%d",&opt,&l,&r,&c);
if(opt==0) add(l,r,c);
if(opt==1) printf("%d\n",val(r));
}
}
```