题目链接：https://www.luogu.org/problemnew/show/P3368
先介绍下差分：
设数组a[]={1,6,8,5,10}，那么差分数组b[]={1,5,2,-3,5}
也就是说b[i]=a[i]-a[i-1];(a[0]=0;)，那么a[i]=b[1]+....+b[i];(这个很好证的)。
假如区间[2,4]都加上2的话
a数组变为a[]={1,8,10,7,10}，b数组变为b={1,7,2,-3,3};
发现了没有，b数组只有b[2]和b[5]变了，因为区间[2,4]是同时加上2的,所以在区间内b[i]-b[i-1]是不变的.
所以对区间[x,y]进行修改,只用修改b[x]与b[y+1]:
b[x]=b[x]+k;b[y+1]=b[y+1]-k;
#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <cmath> #include <queue> using namespace std; int n,m; int input[500010]; int tree[500100]; int lowbit(int x) { return x & -x; } void add(int x,int k) { while(x<=n) { tree[x]+=k; x+=lowbit(x); } } int search(int x) { int ans=0; while(x!=0) { ans+=tree[x]; x-=lowbit(x); } return ans; } int main() { cin>>n>>m; for(int i=1;i<=n;i++) cin>>input[i]; for(int i=1;i<=m;i++) { int a; scanf("%d",&a); if(a==1) { int x,y,z; scanf("%d%d%d",&x,&y,&z); add(x,z); add(y+1,-z); } if(a==2) { int x; scanf("%d",&x); printf("%d ",input[x]+search(x)); } } }