介绍
所谓树状数组，就是将线性的数组预处理成树状的结构以降低时间复杂度。先来看一幅经典的图：
其中的a数组为原生数组，c数组为辅助数组，计算方式为： $$c_1=a_1——{(1)}{10}={(1)}_2$$ $$c_2=a_2+c_1——{(2)}{10}={(10)}_2$$ $$\ldots$$ 不难发现，c[k]存储的实际上是从k开始向前数k的二进制表示中右边第一个1所代表的数字个元素的和。这样写的好处便是可以利用位运算轻松计算sum。上代码。
Code
var
n, i: longint;
a, c: array [1..10000] of longint;
//计算x最右边的1所代表的数字。
继续阅读 »