树状数组(1)

背景：

已知一维数组a[n]，进行如下操作：修改n次\(a_k\)，每次修改完之后立即查询[a,b]的区间和

如果只用前缀和：

1. 每次查询的时间复杂度——\(O(1)\)
2. 修改1次\(a_k\)，需要\(O(n)\)的时间维护前缀和
3. 修改n次\(a_k\)，时间复杂度\(O(n^2)\)

由此，引入树状数组

作用：

解决动态区间的前缀和问题

时间复杂度：

\(O(nlogn)\)

模版：

#define lowbit(x) ((x)&(-x)) 
int n,tree[M],a[M];void update(int x,int d)//修改元素a[x]+=d 并修改tree[x]
{while(x<=n){tree[x]+=d;x+=lowbit(x);}
} int sum(int x)//求[1,x]前缀和
{int ans=0;while(x>0){ans+=tree[x];x-=lowbit(x);}return ans;
}int main()
{cin>>n; for(int i=1;i<=n;++i){cin>>a[i];update(i,a[i]);}cout<<"old:[3,7] "<<sum(7)-sum(2)<<"\n";update(3,-7);cout<<"new:[3,7] "<<sum(7)-sum(2)<<"\n";return 0;
}

样例：

8
5 4 6 5 7 0 1 3

输出：

old:[3,7] 19
new:[3,7] 12