1.2　树状数组

树状数组（Binary Indexed Tree，BIT）能够高效地求序列区间和。树状数组的实现简单，巧妙地运用了二进制的思想。

1.2.1　树状数组的定义

给定一个数组进行两个操作：一是更新某点的值；二是求某段区间的和。对于普通的数组，单点更新的复杂度为O（1），求区间和的复杂度为O（n），而树状数组能够把单点更新和区间求和的复杂度都变为O（nlogn）。

设数组A[]为原数组，定义C[i]=A[i-2k+1]+…+A[i]。其中，k为i用二进制表示时的末尾0的个数，如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[i]就是从A[i]开始前2k项的和，如图1.3所示。

1.2.2　树状数组的实现和使用

k为x用二进制表示时末尾0的个数，对于2k，有一种快速的求解方法：

当修改某一点的值时，只需要修改某一点的所有父节点就可以了。对于一个节点i来说，它的父节点的编号为i+lowbit（i）。因此对于单点修改的函数为

前n个数的和记为sum（n），已知C[i]是从i开始向前lowbit（i）个数的和，所以sum（n）=C[n]+sum[n-lowbit（n）]。

区间[start,end]的区间和可以通过sum（end）-sum（start）来求得。树状数组也可以进行区间增减更新和单点查询操作。A[]是原数组，构造差分数组D[]，令D[1]=A[1]，D[i]=A[i]-A[i-1]（i>1），则数组A是数组D的前缀和，即A[i]=D[1]+D[2]+…+D[i]。这样求A的单点值就是求D的区间和。更新A某段区间[start,end]的值只需要更改D[start]和D[end+1]的值就可以了。这两个操作可以通过构造D的树状数组求得。

1.2.3　例题讲解

例1-1　Sort it

Time Limit:2000/1000 ms（Java/Others）　Memory Limit:32768/32768 KB（Java/Others）

题目描述：

给定一个由n个不同的整数组成的序列，通过交换相邻的两个数，使得序列变成上升的。问最少需要交换多少次，如“1 2 3 5 4”，需要进行一次操作，交换5和4。

输入：

输入包含多组数据，每一组数据包含两行，第一行为一个正整数n（n≤1000），第二行为从1到n的n个整数的一个序列。

输出：

输出为1行，输出最少需要交换的次数。

样例输入：

3

1 2 3

4

4 3 2 1

样例输出：

0

6

题目来源：HDOJ 2689。

解题思路：

题目可以转化成求数组中逆序对的数量。

逆序对：设数组A为一个有n个数字的有序集（n>1），其中的数字均不相同，如果存在正整数i，j，使得1≤i<j≤n而且A[i]>A[j]，则<A[i],A[j]>这个有序对称为A的一个逆序对。

对于每一个数字，求它前面有多少个数字大于它，即该数字的贡献，所有数字的贡献和即逆序对的数量。对于A[i]=x，在树状数组的x处加1，然后求sum（x）就是在x前面有多少个数小于等于x，那么i-sum（x）就是A[i]的贡献。从左到右对于每一个数边插入边求和。

题目实现：