树状数组(1)-为了以后准备用
发布日期:2022-02-08 04:20:47 浏览次数:2 分类:技术文章

本文共 3233 字,大约阅读时间需要 10 分钟。

若要系统的研究树状数组,建议学习一下“二进制分解”“倍增”的概念。 

简介

树状数组是一种可以在O(logn)内完成区间[1,n]的可加性询问(求和,求乘积),在O(logn)内完成单点数据修改的数据结构(以上两种为基本的操作)。 

它的代码量小,常数较小,但是不支持求区间最值(可以使用线段树)。

原理

其实树状数组的核心思想就是倍增,从根本上来说,树状数组是ST算法的强化版。 

ST表主要处理的区间不可加性的问题,而与之类似的树状数组可以求得区间可加性问题。

模板:

int lowbit(int x){    return x&(-x);}int que_sum(int x){    int sum = 0;    for( ; x > 0; x -= lowbit(x))         sum += val[x];    return sum;}void update(int x, int k){    for( ; x <= n; x += lowbit(x))         val[x] += k;}

区间操作可以使用差分,对于一个区间[l,r],我们先处理区间[1,l1],在处理区间[1,r],然后做减法,就可以得到答案。 
对于修改的操作,每次修改一个点,我们只要更新有覆盖这个点的信息段就好了,找到下一个覆盖数字x的信息段的方法是x+=lowbit(x),这样就可以把当前的最低位进位,那个数一定是覆盖修改点里面最小的,这样一直加到大于n就停止。 
这个优化是树状数组对朴素倍增最根本的优化,因为二进制分解的唯一行,所以减少了维护的信息,使维护的信息支持修改,常数变的非常小。 

预备函数[]

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

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

将34转为二进制,为0010 0010,这里的"最后一个1"指的是从{\displaystyle 2^{0}}2^{0}位往前数,见到的第一个1,也就是{\displaystyle 2^{1}}2^{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);}

参考+推荐:

http://blog.csdn.net/yhf_2015/article/details/53844284

http://blog.csdn.net/int64ago/article/details/7429868

http://blog.csdn.net/x_iya/article/details/8943264

维基百科中的说法:

树状数组[]

维基百科,自由的百科全书
根据数组[1, 2, 3, 4, 5]来创建对应的树状数组

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

预备函数[]

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

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

将34转为二进制,为0010 0010,这里的"最后一个1"指的是从{\displaystyle 2^{0}}2^{0}位往前数,见到的第一个1,也就是{\displaystyle 2^{1}}2^{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,用以维护{\displaystyle A}A的前缀和,则:

{\displaystyle BIT_{i}=\sum _{j=i-lowbit(i)+1}^{i}A_{j}}{\displaystyle BIT_{i}=\sum _{j=i-lowbit(i)+1}^{i}A_{j}}

具体能用以下方式实现:(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元素的和//终端结点位置的元素和,将在求和函数中求得

修改[]

假设现在要将{\displaystyle A[i]}A[i]的值增加delta,

那么,需要将{\displaystyle BIT[i]}BIT[i]覆盖的区间包含{\displaystyle A[i]}A[i]的值都加上delta.

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

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

修改函数的C++写法

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

求和[]

假设我们需要计算{\displaystyle \sum _{i=1}^{k}A_{i}}\sum _{​{i=1}}^{​{k}}A_{i}的值.

  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;}

复杂度[]

初始化复杂度最优为{\displaystyle O(N)}O(N)

单次询问复杂度{\displaystyle O(\log N)}O(\log N),其中N为数组大小

单次修改复杂度{\displaystyle O(\log N)}O(\log N),其中N为数组大小

空间复杂度{\displaystyle O(N)}O(N)

应用[]

求逆序数[]

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

从第一个数开始遍历,每次在树状数组中查询有多少个数大于当前的数并加入计数器,之后把当前元素加入树状数组。

转载地址:https://blog.csdn.net/weixin_38960774/article/details/79404701 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:树状数组(2)-为了以后准备用
下一篇:树状数组题

发表评论

最新留言

很好
[***.229.124.182]2024年03月27日 10时44分33秒