树状数组

复习一下树状数组

树状数组

一种用于处理单点修改和区间查询的数据结构。
树状数组C的定义: C[x] = Sum a[x-lowbit(x)+1,x], 即数组C表示原数组某一区间段的和。

lowbit操作

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

单点修改 O(logN)

对于树形结构,我们如果修改一个点的话,对于他祖宗节点的影响是单一的,即我们可以通过一层一层向上更新包含这个节点的所有C数组的值。

int update(int u,int x){
    for(int i = u; i<=n; i+=lowbit(i)){
        c[i] += x;
    }
}

区间查询 O(lonN)

根据树状数组的含义,在求区间和时我们就可以按照如下方法:

Sum(x) = C[x] + C[x-lowbit(x)] + C[y-lowbit(y)] + C[z-lowbit(z)] + ... (x,y,z,....>=0)
其中 y = x-lowbit(x) z = y-lowbit(y)....

为什么这样求是对的呢?
我们将每个C[i] 展开看看,
Sum(x) = C[x] + C[x-lowbit(x)] + ...
Sum(x) = Sum a[x-lowbit(x)+1,x] + Sum a[x-lowbit(x)-(y-lowbit(y)+1, x-lowbit(x)] + ...
这里就可以看出来,其实就是把二进制x每次减去低位1即lowbit(x)
以下图为例, sum(7) = C(7) + C(7-1) + C(6-2) + C(4-4) = C(7) + C(6) + C(4)

BIT

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

可参考学习的博客:
https://www.cnblogs.com/xenny/p/9739600.html

例题

待更

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • lowbit运算:lowbit(x)=x&(-x) //原码与补码相与,取x的二进制最右边的1和它右边的所有0,x...
    Tsukinousag阅读 169评论 0 2
  • 树状数组用来求区间元素和,求一次区间元素和的时间效率为O(logn)。特别用于在数组内的参数变换后,再次求和所使用...
    碧影江白阅读 800评论 1 1
  • 树状数组 前置知识 : 差分&前缀和 位运算 树的基本概念和定理 1. 什么是树状数组? 树状数组(Binary ...
    zhangtianli阅读 168评论 0 1
  • 久违的晴天,家长会。 家长大会开好到教室时,离放学已经没多少时间了。班主任说已经安排了三个家长分享经验。 放学铃声...
    飘雪儿5阅读 7,557评论 16 22
  • 创业是很多人的梦想,多少人为了理想和不甘选择了创业来实现自我价值,我就是其中一个。 创业后,我由女人变成了超人,什...
    亦宝宝阅读 1,865评论 4 1