权和问题
用线性数据结构的方法解决动态统计子树权和的问题
树状数组:也叫二叉索引树,是一个查询和修改复杂度都是$log_2n$d的数据结构,主要用于查询任意两位之间的元素之和。定义如下:
数组$a[]$,元素个数为n,存储在$a[1]~a[n]$中;
子区间的权和数组为$sum$,数组$a$中从$i$到$j$区间内的权和$sum[i,j]=\sum_{k=i}^ja[k]$;
前缀权和数组为s,数组a中长度为$i$的前缀权和$a[i]=\sum_{k=1}^ia[k]$.
$lowbit(k)$为整数k的二进制表示中右边第一个 1 代表的数。 eg:$lowbit(12)=4$
树状数组$c[k]$储存从$a[k]$开始向前数$lowbit(k)$个元素之和
👇图中$c[1]=a[1];c[2]=a[1]+a[2];c[3]=a[3];c[4]=a[1]+a[2]+a[3]+a[4];c[5]=a[5];c[6]=a[5]+a[6]…$
那么数组a的更改和查询在树状数组c中进行。
更改:如果在上例中修改元素$a[2]$,那么只要从$c[2]$开始一层层往上修改即可,时间复杂度为$O(log_2n)$
1 | for(i = k; i < cnt; i += lowbit(i)) |
查找:如果查找$s[7]$,0111右边第一个1在第0位上,也就是要从$a[7]$开始向前数一个元素,也就是$c[7]$,然后去掉1,得到0110,右边第一个1出现在第1位上,也就是要从$a[6]$开始向前数 两个元素,也就是$c[6]$,同理再去掉一个1,也就是$c[4]$,显然,$s[7]=c[7]+c[6]+c[4]$
1 | for(i = x; i > 0; i -= lowbit(i)) |
逆序对
如果$i>j \&\& a[i]<a[j]$,则$a[i]$和$a[j]$为一对逆序对
一个序列中逆序对数就是逆序数
逆序对数计算就是对序列中的每一个数,找出排在其前面有多少个比自己大的数(也可以排在其后面有多少个比自己小的数)。树状数组可以优化这个遍历,方法如下:
递增排序原序列。建立一个元素类型为结构体的数组$a[]$,其中$a[i].val$表示输入的数,$a[i].id$为输入顺序,按$val$为第一关键字,递增排序
利用树状数组的特性求id序列的逆序数(id序列的逆序数==原序列的逆序数)。把id序列中的元素一个一个插入树状数组。我们可以开一个数组b[maxn],来记录前面数据的出现情况,初始化为0;当数据a出现时,就令b[a]=1。这样的话,欲求某个数a的逆序数,只需要算出在当前状态下b[a+1,maxn]中有多少个1,因为这些位置的数在a之前出现且比a大。但是若每添加一个数据a时,就得从a+1到 maxn搜一遍,复杂度太高了。树状数组却能很好的解决这个问题,可以把数一个个插入到树状数组中, 每插入一个数, 统计比他小的数的个数,对应的逆序为 i - getsum( b[i] ),其中 i 为当前已经插入的数的个数, getsum( b[i] )为比 b[i] 小的数的个数,i- getsum( b[i] ) 即比b[i] 大的个数, 即逆序的个数。最后需要把所有逆序数求和,就是在插入的过程中边插入边求和。
举个例子:有5个数,分别为5 3 4 2 1,c为树状数组,当读入数据a=5时,b为:0,0,0,0,1;c为:0,0,0,0,1;当读入数据a=3时,b为:0,0,1,0,1;c为:0,0 , 1,1,1;当读入数据a=4时,b为:0,0,1,1,1;c为:0,0,1,2,1;
此思想的关键在于,读入数据的最大值为maxn,由于maxn较小,所以可以用数组来记录状态。1
2
3
4void Modify(x){
for(int i = x; i <= n;i += lowbit(i))
c[i] += 1;
}
之后通过$getsum()$求出在$[1.x]$有多少个不大于x的数
1 | int getsum(x){ |
之后再用插入的数的个数减去$getsum(x)$的返回值,就是该元素的逆序数,遍历所有元素就是该序列的逆序数。
1 | 递增排序,得排序后的id序列:a[1].id,...,a[n].id |