原题
区间修改，单点求值，那么都需要logn的复杂度，将修改的效果添加到大节点上，向下遍历树，这样最后求单点时向上遍历树。
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<iomanip> #include<algorithm> #define in(x) scanf("%d",&x); using namespace std; int n,m,a[500001],c[500001]; void addhead(int pos,int v) { for(int i=pos;i>0;i-=i&(-i)) c[i]+=v; } int sum(int pos) { int ans=a[pos]; for(int i=pos;i<=n;i+=i&(-i)) ans+=c[i]; return ans; } int main() { in(n);in(m); for(int i=1;i<=n;++i) in(a[i]); for(int i=1;i<=m;++i) { int x,y,s,k; in(s);in(x); if(s==1) { in(y);in(k); addhead(y,k); addhead(x-1,-k); } else { printf("%d\n",sum(x)); } } }
