2014-11-02 Xie Jingyi
介绍 所谓树状数组,就是将线性的数组预处理成树状的结构以降低时间复杂度。先来看一幅经典的图: 其中的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所代表的数字。 继续阅读 »