【数据结构】树状数组

树状数组(Binary Indexed Trees, BIT)是一种玄学数据结构(划掉),基本用途是维护序列前缀和求动态逆序对,能够实现部分线段树功能,且比线段树好写,也比常数和空间复杂度也比线段树小的多(日常黑线段树)。

对于给定的序列a,我们建立一个数组c,其中c[x]保存序列a的区间[x-lowbit(x)+1,x]中所有的数的和,即\sum_{x}^{i=x-lowbit(x)+1}a[i]

如图:

c可以看作一个如上图的树形结构,满足如下性质(BIT性?233):

1.每个内部结点c[x]保存以它为根的子树中所有叶子的和。

2.每个内部结点c[x]的子结点的个数==lowbit(x)

3.除树根外,每个内部结点c[x]的父结点是c[x+lowbit(x)]

4.树的深度是O(\log n)

如果N不是2的整次幂,那么树状数组是一个具有BIT性的森林。

 

树状数组支持两个基本操作:

1.查询前缀和:直接看代码吧,揣摩一下

int sum(int x){
    int ans = 0;
    for(;x;x -= lowbit(x)){
        ans += c[x];
    }
    return ans;
}

2.单点增加,意思是给数组中的一个数a[x]加上y

void add(int x,int y){
    for(;x;x += lowbit(x)){
        c[x] += y;
    }
}

当然这玩意需要初始化:O(n \log n)的方法:

直接建立全0数组c,然后对每个位置x执行add(x,a[x])

发布者:Cinema

成功的道路并不狭窄,因为大部分人都在颓废。

留下评论

电子邮件地址不会被公开。 必填项已用*标注