原题
这是一个模板，奇数点存本身值，偶数点根据其二进制中1的个数存2的n次方个值，这样改值用logn就可以了。
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<iomanip> using namespace std; int n,m,a[500009],c[500009]; int change(int pos,int v) { for(int i=pos;i<=n;i+=i&(-i)) { c[i]+=v; } return 0; } int qusum(int x) { int ans=0; for(int i=x;i>0;i-=i&(-i)) { ans+=c[i]; } return ans; } int main() { cin>>n>>m; for(int i=1;i<=n;++i) scanf("%d",&a[i]); for(int i=1;i<=n;++i) { change(i,a[i]); } for(int i=1;i<=m;++i) { int pop;int x,y; scanf("%d%d%d",&pop,&x,&y); if(pop==1) { change(x,y); } else { cout<<qusum(y)-qusum(x-1)<<endl; } } return 0; }
