树状数组

树状数组

树状数组的核心思想：分治。将数组以二叉树的形式进行维护区间之和。

设$a$为原数组，$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[5]=a[5],t[6]=t[5]+a[6],t[7]=a[7],t[8]=t[4]+t[6]+t[7]+a[8],$…)，即存储$[x-lowbit(x)+1,x]$区间之和。

树状数组的操作：向下查询 向上修改

向下查询：查询前一个能代表其和的元素(例：$sum(4)=t[4],sum(3)=t[3]+t[2],sum(2)=t[2],\dots$)，可发现与下标的二进制表示有关，每次下标更新都在去掉二进制位中的最低的1，这一操作可用$index-=lowbit$实现。

向上修改：向后更新到其所有的代表结点(例：修改$a[3]$，需要修改$t[3]、t[4]、t[8]$)，可以发现每次更新是在下标二进制中最后一个1上+1，因此可通过$index+=lowbit$实现。

注意：0没有$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$加$num$为例)

extern int x,num;
update(x,num);

• 区间查询(以查询$[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]$均加$num$为例)

extern int l,r,num;
update(l,num),update(r+1,-num);

• 单点查询(以查询$x$为例)

extern int x;
query(x);

区间修改+区间查询(二阶树状数组)

(注：此类问题也可采用线段树求解。)

$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$

$=n\sum _{i=1}^n{d}_i-\sum _{i=1}^n(i-1)d_i$(核心公式)

因此，维护两个树状数组，一个用于实现$d_i$，另一个实现$(i-1)d_i$

• 查询函数、修改函数变更为：

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]$均加$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]$为例)(本质：在求前缀和)

extern int l,r;
(r*query1(r)-query2(r))-((l-1)*query1(l-1)-query2(l-1));

应用

求区间之和

以上已给出。

求区间最值

求逆序数