权和问题
用线性数据结构的方法解决动态统计子树权和的问题
树状数组：也叫二叉索引树，是一个查询和修改复杂度都是$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 |