树状数组

维基百科,自由的百科全书
跳转至: 导航搜索
根据数组[1, 2, 3, 4, 5]来创建对应的树状数组

树状数组二叉索引树英语:Binary Indexed Tree),又以其发明者命名为Fenwick树,最早由Peter M. Fenwick于1994年以A New Data Structure for Cumulative Frequency Tables[1]为题发表在SOFTWARE PRACTICE AND EXPERIENCE。其初衷是解决数据压缩里的累积频率(Cumulative Frequency)的计算问题,现多用于高效计算数列的前缀和, 区间和。它可以以的时间得到任意前缀和,并同时支持在时间内支持动态单点值的修改。空间复杂度

结构起源[编辑]

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

基本操作[编辑]

预备函数[编辑]

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

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

将34转为二进制,为0010 0010,这里的"最后一个1"指的是从位往前数,见到的第一个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).

Lowbit的一个简便求法:(C++)

int lowbit(int x)
{
    return x&(-x);
}

新建[编辑]

定义一个数组 BIT,用以维护的前缀和,则:

具体能用以下方式实现:(C++)

void build()
{ 
    for (int i=1;i<=MAX_N;i++)
    {
        BIT[i]=A[i];
        for (int j=i-1; j>i-lowbit(i); j--)
            BIT[i]+=A[j];
    }
}
//注:这里的求和将汇集到非终端结点(D00形式)
//BIT中仅非终端结点i值是 第0~i元素的和
//终端结点位置的元素和,将在求和函数中求得

修改[编辑]

假设现在要将的值增加delta,

那么,需要将覆盖的区间包含的值都加上delta.

这个过程可以写成递归,或者普通的循环.

需要计算的次数与数据规模N的二进制位数有关,即这部分的时间复杂度是O(LogN)

修改函数的C++写法

void edit(int i, int delta)
{
    for (int j = i; j <= MAX_N; j += lowbit(j))
        BIT[j] += delta;
}

求和[编辑]

假设我们需要计算的值.

  1. 首先,将ans初始化为0,将i初始化为k.
  2. 将ans的值加上BIT[i]
  3. 将i的值减去lowbit(i)
  4. 重复步骤2~3,直到i的值变为0

求和函数的C/C++写法

int sum (int k)
{
    int ans = 0;
    for (int i = k; i > 0; i -= lowbit(i))
        ans += BIT[i];
    return ans;
}

复杂度[编辑]

初始化复杂度最优为

单次询问复杂度,其中N为数组大小

单次修改复杂度,其中N为数组大小

空间复杂度

应用[编辑]

求逆序数[5][编辑]

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

参考文献[编辑]