程序猿怎样求数列前n项和
2016-03-29 12:41
已知如下数列：
1,2,1,4,1,2,1,8,1,2,1,4,1,2,1,16,1,2,1,4,1,2,1,8,1,2,1,4,1,2,1,32...
这显然是一个很有规律的数列，但是你能说出规律是什么吗？
其实，将上面的数字换算成二进制，就会看得比较清楚：
1,10,1,100,1,10,1,1000,1,10,1,100,1,10,1,10000...
还是不清楚？那么把每个数字补足4位，然后和一个递增数列并排放在一起看：
0001,0010,0011,0100,0101,0110,0111,1000,1001,1010,1011,1100...（递增）
0001,0010,0001,0100,0001,0010,0001,1000,0001,0010,0001,0100...
可见：将一个递增数列用二进制表示，保留每一项最右边的一个“1”，而将其左边的“1”都变成“0”，即可得到这个数列。
那么，有什么用呢？
其实很有用。我们可以用它来快速求前n项和。
假设我们现在有一组数，比如说，某个月31天之中，每天你的微博获得的点赞数如下：
表一：每天点赞数 [1, 1, 0, 3, 2, 0, 5, 0, 0, 4, 2, 2, 1...]
我们现在想知道“截至某一天的点赞数总计”，也就是求前n项之和。如果每次求和都要做一长串加法那就太费事了。我们完全可以一次性把全部的前n项之和都计算出来：
表二：每天累计点赞数 [1, 2, 2, 5, 7, 7, 12, 12, 12, 16, 18, 20, 21...]
这样一来虽然查询起来很方便，但是如果要修改某个数就会变得很麻烦。比如我们发现表一中第5天的点赞数弄错了，要从2调整到1，那么表二中从第5项开始，后面的每一项都需要修改。
这里提到了两种求前n项和的方法，各有优劣。方法一：不使用表二，每次求和都使用表一重新计算一次，这样求和操作的速度很慢；但是修改操作是瞬间完成的。方法二：花点时间计算产生表二，每次求和都从表二中查询，所以求和操作可以瞬间完成；但是修改一个值的时候需要更新表二中很多的值，所以修改操作会很慢。
那么有没有让求和操作和修改操作都比较快的方法呢？有的。
我们需要的是这样一张表：我们将原始数据表（表三-1），切分成若干个小块，分别对每一个小块进行求和。比如说，我们将相邻的两个数字分成一组，对每组中的两个数字求和，储存在后一个数字上（表三-2）。也就是说，我们将第1、3、5、7、9…项，分别加到第2、4、6、8、10…项上。
表三-1：原始数据 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10...]
表三-2：分组累加 [1, 1+2, 3, 3+4, 5, 5+6, 7, 7+8, 9, 9+10...]
这样一来，如果我们要求前10项之和，只要计算第2、4、6、8、10项之和即可，运算量少了一半。而如果我们要修改第5项的值，受影响的也只是第5、6两项。
求前9项之和可以累加第2、4、6、8、9项得到。
仅仅减少一半的运算量还是不够的。如果数据量非常庞大，比如说要求前十万项数据之和，也还是要进行约五万次加法。把分组设得大一点也不好。比如每1000项分成一组，虽然求前100,000项之和的运算下降到了100次，但是储存着局部和的那些项太稀疏了，如果我们要求前500项之和，没有别的办法，只能从1累加到500。
更好的方法是，在表三-2的基础上，继续对第2、4、6、8、10…项进行分组，也就是将第2、6、10…项，分别加到第4、8、12…项上（表三-3）。
表三-3：分组累加（二阶） [1, 1+2, 3, 1+2+3+4, 5, 5+6, 7, 5+6+7+8, 9, 9+10...]
在这个阶段，求前10项和需要累加第4、8、10项。如果修改第5项的值，影响的是第5、6、8项。
我们继续上述过程，每次都将上一次用来储存局部和的那些项（比如在表三-3中就是第4、8、12…项）两两分组相加，最后就会得到表三-4。
表三-4：分组累加（终极） [1, 1~2, 3, 1~4, 5, 5~6, 7, 1~8, 9, 9~10, 11, 9~12, 13, 13~14, 15, 1~16...]
表三-4已经不能再分组相加了。每进行上述过程一次，下次用来分组相加的那些项就会减少一半。除非数据量是无限的，否则总会加到山穷水尽。
表三-4有什么特性呢？
一、它的求和操作和修改操作速度都非常快，虽然做不到瞬间完成，但难得的是两者一样快，都不会拖后腿。
比如我们要求前100,000项之和，需要累加的是第65536（包含1～65536）、98304（包含第65537～98304）、99328（包含第98305～99328）、99840（包含第99329～99840）、99968（包含第99841～99968）、100000（包含第99969～100000）项，一共6项。
六项！刚才还说要累加五万项，一下子减成了六项。所以说为什么要学算法！
实际上，利用这个方法求前n个数之和，所需的加法操作在log(n)次以内。对于十几万这个数量级，最多也不过是十五六次加法。
而如果我们要修改某一项的值，比如第5项，在前十万项之内需要相应地更新的项包括：第5、6、8、16、32、64、128、256…65536项，一共16项。我们无需做任何累加操作。只要知道第5项和原先相比增加（或减少）了多少，将这个增量加到这16项上面就完成了。
二、观察一下表三-4中每一项分别代表原始数据（表三-1）中的几项之和？
分别是：1,2,1,4,1,2,1,8,1,2,1,4,1,2,1,16,1,2,1,4,1,2,1,8,1,2,1,4,1,2,1,32…
就是一开始我们遇到的那个数列。
三、前32项的情况请看示意图：
横向看可以看到每一项包含了前面哪些项之和；纵向看可以看到每一项分别都包含在哪些项之中。
可以发现，所有奇数项都只包含它自身的值；所有2的n次方项都包含了从1到2的n次方这么多项的总和。更一般地说，表三-4中每一项所对应的是：表三-1中从某个小于等于它的项开始、一直到它自身的一段连续的项之和。
如果想知道具体如何计算各项包含的和，用二进制可以解释得更清楚些。假设我们想看第104项是哪些项之和。首先这些项肯定是连续的，最大的那一项就是104本身。最小一项怎么求呢？我们将104写成二进制0110 1000。注意它的最后一个“1”位于从右边数第4位上。我们将这一位变成“0”，得到0110 0000；然后再加1，得到0110 0001。这个就是104所包含的最小项，换算成十进制是97。所以表三-4第104项就是表三-1中第97至104项之和。
四、虽然也说不上是缺点，但这种方法和之前的两种比起来，较慢的操作是建立表三-4本身。假设原始数据（表一）含有n个项。之前提到的方法一仅使用表一就能计算，无需建立辅助表；方法二从第一项开始累加生成表二，也就是说表二的建立需要进行约n次加法；而表三-4的建立要进行n·log(n)次这个数量级的加法运算。对于十万项这么大的数据量，建立表三-4大约要进行百万次左右加法。所以这种方法所适合的场合是：一次建立后，多次查询，多次修改。这样它的优势就会发挥出来。
顺便提一下，表三-4这种数据结构有个名字，叫做Binary Indexed Tree，也叫Fenwick Tree。中文维基翻译成树状数组。
下面我们看一下如何用程序实现上述过程。
正如上面提到的，我们需要进行“辅助表的建立”、“查询前i项之和”、“修改第i项的值”三种操作。实际上，表的建立相当于是针对一张全都是0的表，依次修改各项的值为初始值。所以说到底我们只需要两种操作：求和和修改。
首先假设我们已经有了这个辅助表，它可以是一个一维的数组，比如就叫BIT[]好了。BIT是Binary Indexed Tree的缩写。
先来看求和操作。比如我们要求前104项之和。用二进制数来说就是要求前0110 1000项之和。也就是从0000 0001项一直加到0110 1000项。我们先声明一个变量sum = 0。
上面已经提到，BIT[]中的第0110 1000项已经包含了0110 0001～0110 1000这么多项之和。所以我们先让sum += BIT[104]。这样就还剩下0000 0001～0110 0000这些项。
接下来我们看0110 0000这一项。通过上面说的计算方式可以发现，它正好包含了0100 0001～0110 0000这些项之和。所以我们再让sum += BIT[96]（0110 0000换算成十进制是96）。这样就还剩下0000 0001～0100 0000这些项。
最后，我们发现，第0100 0000（换算成十进制是64）项恰好包含了剩余的全部项之和，所以只要让sum += BIT[64]，这样就完成了。
0000 0001～0100 0000, 0100 0001～0110 0000, 0110 0001～0110 1000
回顾以上过程可以看出，我们将要求和的数写成二进制，找到它最右边的“1”，将其变成“0”，就得到了下一个需要累加的项。重复这个过程直到所有的“1”都变成“0”，结束。比如0110 1000，我们第一步需要的是0000 1000这个数，计算0110 1000 - 0000 1000，就可以得到我们需要的下一项0110 0000。
在编程中，用什么方法可以快速从0110 1000计算得到0000 1000呢？从右向左遍历二进制中的每一位当然是一种方法，但是有更好的方法：假设要求和的数是i，只要计算i & -i（”&”是按位与运算），就得到了所需的数。比如计算104 & -104。这里假设我们用8位二进制数来表示[-128, 127]区间内的整数，104 和 -104换成二进制分别是0110 1000 和 1001 1000，按位做AND运算就得到了0000 1000。
对递增数列[1,2,3,4,5…]的每一项i分别计算i & -i，就会得到[1,2,1,4,1,2,1,8…]。
为什么i & -i会得到“i最右边的1”这个数呢？这和计算机对负数的二进制定义有关。我们知道，计算机中负数的二进制表示方法是这样的：
如果i是正整数，-i的二进制数是对i按位求反（1变0，0变1），结果再加1。
这样定义的道理在于：计算机通常用32位二进制数来表示一个整数。1的二进制数是0000…0001，用上述方法计算出的-1的二进制数就是1111…1111（0000…0001按位求反得到1111…1110，再加1即得结果）。这样一来就有个好处：如果我们根据二进制加法的规则计算1111…1111 + 1，结果保留右边32位，就得到了0000…0000。正好符合-1 + 1 = 0的事实。同样可以验证-2 + 1 = -1。所以，正负二进制数可以采用相同的加法操作。因此这样定义负数的二进制是非常自然的。
明白了这一点再来看i & -i。我们关注的是i的二进制数中最右边的那个“1”。显然，这个“1”的右边可能会有若干个0，也可能没有；左边则有一些混杂的1和0。因此，我们可以将i的二进制数表示成“a1b”的形式，a是左边那些1/0，b是右边的一串0。b也可能是空的，这不要紧。
现在我们看-i，它是对a1b按位求反，再加1。
a1b按位求反，就是分别对a、1、b按位求反，得到了a'0b'，其中b'是一串1。
再对它加1，由于b'是一串1，加1的结果就是不停进位，最后0b'变成了1b。所以-i的二进制数可以表示成a'1b。
然后我们计算a1b & a'1b。a和a'互反，按位AND的结果是统统变成0；1 AND 1还是1；b是一串0，按位AND完还是0。所以a1b & a'1b的结果就是：只有这个最右边的“1”还是1，其他位上都变成0了。
总结一下，BIT数组求前i项和的伪代码可以写为：
getSum(i):
sum = 0
while i > 0:
sum += BIT[ i ]
i -= i & -i
return sum
然后再来看修改操作。假设我们要对原始数据的第i项进行修改，给它加上一个增量delta。我们现在要做的是找出BIT[ ]中哪些项包含了第i项，给它们分别加上delta。
如果函数参数给的不是delta，而是“将第i项的值重设为val”，那么可以用val减去第i项的旧值计算出delta。
将上面求和操作的过程逆转来想一下：对于第i项（i可以表示为“a1b”的形式），下一个包含它的值的项（比如称作第j项，显然有j > i），其二进制数和“a1b”有什么样的关系？或者说，j的二进制数中最右边的“1”应该处于什么位置？
我们发现，j中最右边的“1”，应该位于i的二进制数“a1b”中的“a”之内，而且是a1b的那个“1”的左边的第一个“0”。也就是说，我们可以把“a1b”进一步写成“c0d1b”，其中c0d = a；“0”就是j的二进制数中最右边的“1”的位置；d是一串连续的1，可以为空。
如果“a”之内没有0（除了最左边一位以外）该怎么办呢？那就说明下一个包含i的值已经超过了32整数能表示的范围，可以不用考虑了。
由此我们就得到了j的二进制表示法：“c1e”，e是连续的0。
i：c（1/0混杂）- 0 - d（连续1）- 1 - b（连续0）
j：c（1/0混杂）- 1 - e（连续0）
所以我们需要根据“c0d1b”来求出“c1e”。注意“b”和“e”分别都是连续的0，“d1”则是连续的1。很明显，我们只需要做一个加法，在“c0d1b”中的“1”那一位上加上一个1，就好了。而这个要加的数，正是我们已经见过多次的“i & -i”。 所以BIT数组修改第i项值的伪代码可以写为：
update(i, delta):
while i < 数组边界:
BIT[ i ] += delta
i += i & -i
以上就是如何利用Binary Indexed Tree求数组前n项和的方法。正如上面提到的，这种方法初始化辅助表的时间复杂度是O(N·logN)；查询和修改操作的时间复杂度都是O(logN)；空间复杂度是O(N)，因为要建立和原始数据同样规模的辅助表BIT[]。
Binary Indexed Tree还有别的用法。例如在2D方向上建立BIT[][]，快速计算2D表格中某一格的左上方矩形区域内的各项和。进而可以计算2D表格中以任意两点作为左上角和右下角所确立的矩形区域中的各项和。