侧边栏壁纸
博主头像
Hope博主等级

努力赚钱的工科研究生

  • 累计撰写 362 篇文章
  • 累计创建 129 个标签
  • 累计收到 5 条评论
标签搜索

树状数组

Hope
2022-09-22 / 2 评论 / 5 点赞 / 1,497 阅读 / 2,000 字
温馨提示:
本文最后更新于 2022-09-22,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

参考下面两个博客
树状数组(简单介绍)
树状数组详解

数组数组解决的问题:

  1. 输入一个数m,输出数组中下面1 ~ m的前缀和
  2. 对某个指定下标的数进行值的修改,同时影响到前缀和数组。

如果使用差分数组操作,第二个操作是O(n^2)的复杂度。
而使用树状数组复杂度可以达到O(logn)的复杂度

数装数组的思想就是通过二进制来维护数组的信息。
可以看如下的数组图片,就可以理解为什么叫“树状”
image.png
通过变换之后,
image.png

如图,对于一个长度为n的数组,A数组存放的是数组的初始值,引入一个辅助数组C;

image.png
则有如下信息:
C1 = A1
C2 = C1 + A2 = A1 + A2
C3 = A3
C4 = C2 + C3 + A4 = A1 + A2 + A3 + A4
C5 = A5
C6 = C5 + A6 = A5 + A6
C7 = A7
C8 = C4 + C6 + C7 + A8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8

称C[i]的值为下标为i的数所管辖的数的和,下标为i的数所管辖的元素的个数为2 ^ k个(k为i的二进制的末尾的0的个数),C数组不是前缀和的数组。

例如:

  1. i = 8 = 1000, 末尾有3个0, 故k = 3,所管辖的个数为2 ^ 3 = 8,C8是8个数的和;
  2. i = 5 = 0101, 末尾没有0,故k = 0,所管辖的个数为2 ^ 0 = 1,C5是一个数的和。

而对于输入的数m,我们要求编号为m的前缀和A1,...,Am,按照上面说的,SUMm = Ci1 + Ci2 + ,...,这里的m和C[i]的对应关系式这样的,对于查询m,将它转换为二进制后,不断对末尾的1的位置进行-1操作,知道全部为0停止,中间得到的值就是C[i],例如:

  1. m = 7,SUM7 = C7 + C6 + C4,7的二进制为0111,对于0111的末尾1的位置-1,得到0110 = 6(C6得到),再对0110末尾1位置-1,得到0100 = 4(C4得到),最后对0100末尾1位置-1后得到0000(结束),计算停止,至此C7,C6,C4全部得到,求和后就是m = 7时它的前缀和。
  2. m = 6, SUM6 = C6 + C7,6的2进制等于0110,经过两次变换后为0100和0000,那么求和后同样也得到了预计的后果。

那么求前缀和的代码如下:

int lowbit(int m){
	return m & (-m);
}
int getSum(int m){
	int ans = 0;
    while(m > 0){
        ans += C[m];
        m -= lowbit(m);
    }
    return ans;
}

建立数组数组

对于一个输入的数组A,我们一次读取的过程,就可以想成一个不断更新值的过程,所以建树与单点更新值是一样的,即把A1,...,An从0更新成我们输入的A[i],所以一边读入A[i],一边讲C[i]涉及的祖先节点更新,完成输入后数妆数组C也就建立成功了。

更新节点值:

image.png

假设更新A[2] = 5,通过观察我们得知,如果修改了A[2]的值,那么管辖A[2]的C[2],C[4],C[8]的前缀和都要加上5(所有的祖先节点),那么和查询类似,我们如何得到C2的所有祖先节点呢,依旧是上述的巧妙的方法,但是我们把它倒过来用,对于要更新i位置的值,我们把i转换成二进制,不断对二进制最后一个1的位置+1,直到达到数组下标的最大值n结束,对于给出的例子i = 2,假设数组下标上限n = 8,i转换成二进制后等于0010(C2),对末尾1的位置进行+1,得到0100(C4),对末尾的1的位置进行+1,得到1000(C8),循环结束,对C2, C4, C8的前缀和都要+5,当然不能忘记对A[2]的值+5,单点更新值过程结束。

void update(int x, int value){
    A[x] += value;	// 修改源数组
    while(x <= n){
        C[x] += value;
        x += lowbit(x);
    }
}

主要代码

#include<stdio.h>
#include<string.h>

int a[10005];
int c[10005];
int n;

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

int getSum(int x){
    int ans = 0;
    while(x > 0){
        ans += c[x];
        x -= lowbit(x);
    }
    return ans;
}

void update(int x, int value){
    a[x] += value;
    while(x <= n){
        c[x] += value;
        x += lowbit(x);
    }
}

int main(){
    while(scanf("%d", &n)!=EOF){
        memset(a, 0, sizeof(a));
        memset(c, 0, sizeof(c));
        for(int i = 1; i <= n; i++){
            scanf("%d", &a[i]);
            update(i, a[i]);
        }
        int ans = getSum(n-1);
        printf("%d\n", ans);
    }   
    return 0;
} 

5

评论区