引子
树状数组是一种支持单点修改和区间查询码量低常数小的数据结构。
任何数字都可以表示为不超过logn个2的幂次之和，例如7=4+2+1，这一特性就是树状数组的核心理论。
关键在于设计一种数据结构，使得任意前缀和都能由logn个区间和表示以及每个位置最多被logn个区间覆盖，这样就能实现单点修改和区间查询。
树状数组通过lowbit运算实现这一目标。lowbit定义为数字二进制表示中最右边的1所代表的值，可通过x&-x快速计算。例如6的lowbit是2(110)、8的lowbit是8(1000)
在具体实现中，t[i]存储以 i 为右端点长度为lowbit(i)的区间和，前缀和计算采用递推的方式sum(7)=t[7]+t[6]+t[4]，其中6=7-lowbit(7)、4=6-lowbit(6)
单点更新时，由于t[i]包含位置 i，所以只需要沿着lowbit递增的方向更新所有相关区间就行了，同样利用lowbit实现高效处理。
B3612 【深进1.例1】求区间和
虽然这道题用前缀和比树状数组快一倍，但如果用树状数组写的话呃比模板题会简单一些。
#include<bits/stdc++.h>usingnamespacestd;//树状数组参考模板ints[100005],n;intlowbit(intx){//lowbit函数returnx&(-x);}voidadd(inti,intx){//递增for(;i<=n;i+=lowbit(i))s[i]+=x;}intsum(inti){//求区间和intsm=0;for(;i>0;i-=lowbit(i))sm+=s[i];returnsm;}intmain(){cin>>n;for(inti=1;i<=n;i++){intx;cin>>x;add(i,x);//递增}intm;cin>>m;while(m--){intl,r;cin>>l>>r;cout<<sum(r)-sum(l-1)<<endl;//前缀和}return0;}P3374 【模板】树状数组 1
单点修改和区间查询。
这里说明一下树状数组是可以中途单点修改的。
#include<bits/stdc++.h>usingnamespacestd;ints[500005],n;intlowbit(intx){returnx&(-x);}voidadd(inti,intx){for(;i<=n;i+=lowbit(i))s[i]+=x;}intsum(inti){intsm=0;for(;i>0;i-=lowbit(i))sm+=s[i];returnsm;}intmain(){intm;cin>>n>>m;for(inti=1;i<=n;i++){intx;cin>>x;add(i,x);}while(m--){intopt,x,y;cin>>opt>>x>>y;if(opt==1){//这里判断一下是单点修改还是区间查询add(x,y);}else{cout<<sum(y)-sum(x-1)<<endl;//还是前缀和}}return0;}P3368 【模板】树状数组 2
区间修改和单点查询。
首先直接x到y都递增一次会发现TLE70分，于是考虑用树状数组维护一个差分数组，三函数一样，输入a数组时add(a[i]-a[i-1])；要区间修改时add(l,k)add(r+1,k)，还是差分；单点查询时输出sum(x)，相当于差分之后进行一次前缀和。
#include<bits/stdc++.h>usingnamespacestd;inta[500005],s[500005],n;intlowbit(intx){returnx&(-x);}voidadd(inti,intx){for(;i<=n;i+=lowbit(i))s[i]+=x;}intsum(inti){intsm=0;for(;i>0;i-=lowbit(i))sm+=s[i];returnsm;}intmain(){intm;cin>>n>>m;for(inti=1;i<=n;i++){cin>>a[i];add(i,a[i]-a[i-1]);}while(m--){intopt;cin>>opt;if(opt==1){intx,y,k;cin>>x>>y>>k;add(x,k);add(y+1,-k);}else{intx;cin>>x;cout<<sum(x)<<endl;}}return0;}
