高效维护区间之和/区间最值的数据结构(一)——树状数组
树状数组的核心思想：分治。将数组以二叉树的形式进行维护区间之和。
设 a a a为原数组， t r e e tree tree为树状数组。 t r e e tree tree数组用于存储树上该结点下严格直连的子节点之和(例： t [ 1 ] = a [ 1 ] , t [ 2 ] = t [ 1 ] + a [ 2 ] , t [ 3 ] = a [ 3 ] , t [ 4 ] = t [ 2 ] + t [ 3 ] + a [ 4 ] t[1]=a[1],t[2]=t[1]+a[2],t[3]=a[3],t[4]=t[2]+t[3]+a[4] t[1]=a[1],t[2]=t[1]+a[2],t[3]=a[3],t[4]=t[2]+t[3]+a[4]， t [ 5 ] = a [ 5 ] , t [ 6 ] = t [ 5 ] + a [ 6 ] , t [ 7 ] = a [ 7 ] , t [ 8 ] = t [ 4 ] + t [ 6 ] + t [ 7 ] + a [ 8 ] , t[5]=a[5],t[6]=t[5]+a[6],t[7]=a[7],t[8]=t[4]+t[6]+t[7]+a[8], t[5]=a[5],t[6]=t[5]+a[6],t[7]=a[7],t[8]=t[4]+t[6]+t[7]+a[8],…)，即存储 [ x − l o w b i t ( x ) + 1 , x ] [x-lowbit(x)+1,x] [x−lowbit(x)+1,x]区间之和。
树状数组的操作：向下查询 向上修改
向下查询：查询前一个能代表其和的元素(例： s u m ( 4 ) = t [ 4 ] , s u m ( 3 ) = t [ 3 ] + t [ 2 ] , s u m ( 2 ) = t [ 2 ] , … sum(4)=t[4],sum(3)=t[3]+t[2],sum(2)=t[2],… sum(4)=t[4],sum(3)=t[3]+t[2],sum(2)=t[2],…)，可发现与下标的二进制表示有关，每次下标更新都在去掉二进制位中的最低的1，这一操作可用 i n d e x − = l o w b i t index-=lowbit index−=lowbit实现。
向上修改：向后更新到其所有的代表结点(例：修改 a [ 3 ] a[3] a[3]，需要修改 t [ 3 ] 、 t [ 4 ] 、 t [ 8 ] t[3]、t[4]、t[8] t[3]、t[4]、t[8])，可以发现每次更新是在下标二进制中最后一个1上+1，因此可通过 i n d e x + = l o w b i t index+=lowbit index+=lowbit实现。
注意：0没有 l o w b i t lowbit lowbit，因此树状数组下标必须从1开始。
lowbit函数的实现
int lowbit(int i){
return i&(-i);
}
修改函数的实现(向上修改)
void update(int i,int num){//向上修改
for(;i<=N;i+=lowbit(i))
tree[i]+=num;
}
查询函数的实现(向下查询)
int query(int i){//向下查询
int ans=0;
for(;i>=1;i-=lowbit(i))//注意tree数组下标从1开始
ans+=tree[i];
return ans;
}
单点修改 区间查询(前缀和版树状数组)
- 初始化
void init(){//初始化tree数组
for(int i=1;i<=n;i++)//注意tree数组下标从1开始
update(i,a[i]);//在初始化tree数组时num所传入参数为原数组值
}
- 单点修改(以将 x x x加 n u m num num为例)
extern int x,num;
update(x,num);
- 区间查询(以查询 [ l , r ] [l,r] [l,r]为例)
extern int l,r;
query(r)-query(l-1);
区间修改 单点查询(差分版树状数组)
- 初始化
void init(){
for(int i=1;i<=n;i++)
update(i,a[i]-a[i-1]);//num传入差分数组
}
- 区间修改(以 [ l , r ] [l,r] [l,r]均加 n u m num num为例)
extern int l,r,num;
update(l,num),update(r+1,-num);
- 单点查询(以查询 x x x为例)
extern int x;
query(x);
区间修改+区间查询(二阶树状数组)
(注：此类问题也可采用线段树求解。)
a 1 + a 2 + . . . + a n = d 1 + ( d 1 + d 2 ) + . . . + ( d 1 + . . . + d n ) = n × d 1 + ( n − 1 ) × d 2 + . . . + d n a_1+a_2+...+a_n=d_1+(d_1+d_2)+...+(d_1+...+d_n)=n\times d_1+(n-1)\times d_2+...+d_n a1+a2+...+an=d1+(d1+d2)+...+(d1+...+dn)=n×d1+(n−1)×d2+...+dn
= n ∑ i = 1 n d i − ∑ i = 1 n ( i − 1 ) d i =n\sum\limits_{i=1}^{n} d_i-\sum\limits_{i=1}^{n}(i-1)d_i =ni=1∑ndi−i=1∑n(i−1)di(核心公式)
因此，维护两个树状数组，一个用于实现 d i d_i di，另一个实现 ( i − 1 ) d i (i-1)d_i (i−1)di
- 查询函数、修改函数变更为：
void update1(int i,int num){
for(;i<=n;i+=lowbit(i))
t1[i]+=num;
}
void update2(int i,int num){
for(;i<=n;i+=lowbit(i))
t2[i]+=num;
}
int query1(int i){
int ans=0;
for(;i>=1;i-=lowbit(i))
ans+=t1[i];
return ans;
}
int query2(int i){
int ans=0;
for(;i>=1;i-=lowbit(i))
ans+=t2[i];
return ans;
}
- 初始化函数(按照推导公式)
void init(){
for(int i=1;i<=n;i++){
update1(i,a[i]-a[i-1]);//对tree1传入差分数组
update2(i,(i-1)*(a[i]-a[i-1]));//对tree2传入(i-1)*差分数组
}
}
- 区间修改(以 [ l , r ] [l,r] [l,r]均加 n u m num num为例)
extern int l,r,num;
update1(l,num),update1(r+1,-num);//对tree1加上差值
update2(l,(l-1)*num),update2(r+1,(r+1-1)*(-num));//对tree2加上差值(根据推导公式)
- 区间查询(以查询 [ l , r ] [l,r] [l,r]为例)(本质：在求前缀和)
extern int l,r;
(r*query1(r)-query2(r))-((l-1)*query1(l-1)-query2(l-1));