大家好，我是div.2的垫底选手，本期由我来为大家介绍一个实用的区间信息维护与查询的数据结构——二叉索引树，又名树状数组，Fenwick。
(->)
对于动态连续和查询问题。给定一个n个元素的数组A1.A2,...,An，我们想设计一种数据结构，支持以下两种操作：Add(x,d)...和Query(L,R)...，并且让Query和Add都快速完成。如果用简单的前缀和来做的话，预处理会花费O(n)的时间，这样虽然查询是O(1)的，但每次Add操作却是O(n)的，总的时间复杂度是平方级的，还是会很慢。本期要介绍的二叉索引树就可以很好地解决这个问题。
(->)
我们先来理解一下树状数组中的"树状"的意思。这是一个下标从下向上生长的数组，下标已经用二进制表示出来（0,1,2...）。注意，下标0我们丢弃不用，他不是树的一部分。
(mouse pointer as oen)
观察每个下标的二进制表达式中最右边的1的位置(圈起来), 我们发现这刚好是一个树形的结构(每个节点连起来)。
(->)
我们定义lowbit(x)为x的二进制表达式中最右边的1所对应的值(而不是这个比特的序号)。比如...(划图)。在程序实现中(->)。这是因为计算机里的整数采用补码表示，因此-x实际上是x按位取反，末尾加1以后的结果(画图)；二者按位取“与”之后，前面的部分全部便0,之后lowbit保持不变。 在这颗二叉索引树中，每一层节点的lowbit相同(画图)，而且lowbit越大，越靠近根。
对于节点i，如果它是左子节点，那么父节点的编号就是i+lowbit(i)；如果它是右子结点，那么父节点的编号是i-lowbit(i)[鼠标指示示意] 搞清楚树的结构之后，构造一个辅助数组fi.换句话说，f的每个元素都是A数组中的一段连续和，例如[画笔勾画举例].在二叉索引树中，(->)每个结点都属于一个以他自身结尾的水平长条[对于lowbit=1的那些点，长度就是那个结点自己]，这个长条中的数之和就是f[i](<-黑图消失)，例如结点i的长条就是从x~y,即C=A+A+A+..+A.
有了f数组后，就可以快速的完成查询和修改两个操作.
(->)顺着节点i往下爬，边走边往左走(注意不一定沿着树中的边爬)，把沿途经过的f[i]累加起来就可以了(用pen比划)。而如果修改了A[i],只需从f[i]开始往上爬(同样不一定沿着树中的边爬)，边爬边往左走，修改沿途所有节点对应的f[i]既可[用pen比划]. 两个操作的伪代码如下(稍微注释一下)(->)(->)
不难证明，两个操作的时间复杂度均为O(logn)。预处理的方法是先把f数组清空，然后执行n次add操作，总时间复杂度是O(nlogn)。
下面我们用一道例题来简单说明一下Fenwick树的实际应用, 我们来看Codeforces Round #261(Div.2)的D题.
题意很简单，给你n个整数, f(l,r,x)表示下标在[l,r]中的数x的个数。计算有多少对i,j (1 ≤ i < j ≤ n) 使得 f(1, i, ai) > f(j, n, aj).
我们用c[i]表示f(1,i,ai)，也即是1i中ai的值出现的次数, 这个可以从左到右扫一遍得到. 用d[j]表示f(j,n,aj),也即是jn中aj的值出现的次数，这个也可以从右往左扫一遍得到.
(切到gimp边讲边画)
现在问题变成了有多少对i,j(1 ≤ i < j ≤ n)使得c[i]>d[j]，用g[i]表示对于特定的i满足条件的j的个数.
于是我们可以从右向左扫描所有的d[j], 令count[x]表示已扫过的d[j]中值为x的个数，则g[i]就是前缀和count[1]+count[2]+..+count[c[i]-1].初始时所有count[i]=0, 在计算g[i]时，需要先令count[d[i+1]]++，再求前缀和。换句话说，我们需要动态地修改单个元素值并求前缀和——这正是树状数组的标准用法。(边编码边说)这样O(nlogr)(r是c[i]和d[i]的上限)的时间内计算出所有的g[i]，然后再O(n)的时间里累加出最后的答案.
……