树状数组或二叉索引树（英语：Binary Indexed Tree），又以其发明者命名为Fenwick树，最早由Peter M. Fenwick于1994年以A New Data Structure for Cumulative Frequency Tables为题发表在SOFTWARE PRACTICE AND EXPERIENCE。其初衷是解决数据压缩里的累积频率（Cumulative Frequency）的计算问题，现多用于高效计算数列的前缀和， 区间和。

树状数组或二叉索引树（英语：Binary Indexed Tree），又以其发明者命名为Fenwick树，最早由Peter M. Fenwick于1994年以A New Data Structure for Cumulative Frequency Tables为题发表在SOFTWARE PRACTICE AND EXPERIENCE。其初衷是解决数据压缩里的累积频率（Cumulative Frequency）的计算问题，现多用于高效计算数列的前缀和， 区间和。

按照Peter M. Fenwick的说法，正如所有的整数都可以表示成2的幂和，我们也可以把一串序列表示成一系列子序列的和。采用这个想法，我们可将一个前缀和划分成多个子序列的和，而划分的方法与数的2的幂和具有极其相似的方式。一方面，子序列的个数是其二进制表示中1的个数，另一方面，子序列代表的f[i]的个数也是2的幂。

定义一个Lowbit函数，返回参数转为二进制后,最后一个1的位置所代表的数值.

例如,Lowbit(34)的返回值将是2；而Lowbit(12)返回4；Lowbit(8)返回8。

位往前数,见到的第一个1,也就是位上的1.

程序上，((Not I)+1) And I表明了最后一位1的值,

仍然以34为例,Not 0010 0010的结果是 1101 1101(221),加一后为 1101 1110(222), 把 0010 0010与1101 1110作AND,得0000 0010(2)。

逆序数是一个数列中在它前面有比它大的个数。如4312的逆序数是0+1+2+2=5。

从最后一个数开始遍历，每次在树状数组中查询有多少个数小于当前的数并加入计数器，之后把当前元素加入树状数组。