树状数组可以解决什么样的问题:
这里通过一个简单的题目展开介绍, 先输入一个长度为 n 的数组, 然后我们有如下两种操作:
输入一个数 m, 输出数组中下标 1~m 的前缀和
对某个指定下标的数进行值的修改
多次执行上述两种操作
寻常方法
对于一个的数组, 如果需要求 1~m 的前缀和我们可以将其从下标 1 开始对 m 个数进行求和, 对于 n 次操作, 时间复杂度是 O(n^2), 对于值的修改, 我们可以直接通过下标找到要修改的数, n 次操作时间复杂度为 O(n), 在数组 n 开得比较大的时候, 求前缀和的效率显得低了
那么有人提出了一种优化的方式:
初始我们用一个数组 A 的保存每个位置的初始值, 然后用一个辅助数组 B 存放的是下标为 i 的时候 A 数组的前 i 个的和 (前缀和), 那么当我们需要查询 m 个数的前缀和的时候只要直接使用下标对 B 数组进行查询即可, n 次查询, 时间复杂度为 O(n), 而此时, 对于单点更新值的维护消耗, 由原来的 O(n) 变成了 O(n^2), 因为每一次与更新单点值都会对后面的已经计算好的 B 数组前缀和的值造成影响, 需要不断更新 B 数组的值, n 次更新维护的消耗自然就变成了 O(n^2), 更新的效率变得低下
树状数组
那么是否有一种方法可以让查询和更新的时间复杂度都小一些呢, 至少可以令人接受, 这里将介绍树状数组如何处理前缀和查询和单点更新的问题, 对于 n 次操作, 时间复杂度都为 O(nlogn)
借用百度百科上的图片
如图, 对于一个长度为 n 的数组, A 数组存放的是数组的初始值, 引入一个辅助数组 C(我们通过 C 数组建立树状数组)
- 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 的数所管辖的数的和, C[8]存放的就是被编号 8 所管辖的那些数的和 (有 8 个), 而下标为 i 的数所管辖的元素的个数则为 2^k 个(k 为 i 的二进制的末尾 0 的个数) 举两个例子查询下标 m==8 和 m==5 所管辖的数的和
8 = 1000, 末尾 3 个 0, 故 k == 3, 所管辖的个数为 2^3 == 8,C8 是 8 个数的和
5 = 0101, 末尾没有 0, 故 k == 0, 所管辖的个数为 2^0 == 1,C5 是一个数的和(它本身 A5)
而对于输入的数 m, 我们要求编号为 m 的数的前缀和 A1~Am(这里假设树状数组已经建立, 即 C1~C8 的值已经求出, 别着急, 在本文的最下方会做出建立树状数组的过程讲解, 因为现在是在求前缀和, 就假设 C 数组已经可用了吧)举两个例子 m==7 和 m==6(sum(i)表示求编号为 i 的前缀和)
m==7 sum(7) = C7 + C6 + C4
那么我们是怎么得到编号 7 是由哪几个 C[i]求和得到呢(C4, C6, C7 怎么得到的), 这里有介绍一种巧妙的方法:
对于查询的 m, 将它转换成二进制后, 不断对末尾的 1 的位置进行 - 1 的操作, 直到全部为 0 停止
7 的二进制为 0111(C7 得到), 那么先对 0111 的末尾 1 的位置 - 1, 得到 0110 == 6(C6 得到), 再对 0110 末尾 1 位置 - 1, 得到 0100 == 4(C4 得到), 最后对 0100 末尾 1 位置 - 1 后得到 0000(结束信号), 计算停止, 至此 C7,C6,C4 全部得到, 求和后就是 m == 7 时它的前缀和
m==6 sum(6) = C6 + C4
m == 6 时也是一样, 先转成 2 进制等于 0110, 经过两次变换后为 0100(C4)和 0000(结束信号), 那么求和后同样也得到了预计的结果
这里要介绍一个高效的方法, lowbit(int m), 这是一个函数, 它的作用是求出 m 的二进制表示的末尾 1 的位置, 对于要查询 m 的前缀和, m = m - lowbit(m)代表不断对二进制末尾 1 进行 - 1 操作, 不断执行直到 m == 0 结束, 就能得到前缀和由哪几个 Cm 构成, 十分巧妙, lowbit 也是树状数组的核心
- int lowbit(int m){
- return m&(-m);
- }
关于 m&(-m)很多童鞋可能感到困惑, 那么就不得不提及一下负数在计算机内存中的存储形式, 负数在计算机中是以补码的形式存储的, 如 13 的二进制表示为 1101, 那么 - 13 的二进制而将 13 二进制按位取反, 然后末尾 + 1, 即 0010 + 0001 = 0011, 那么 1101 & 0011== 0001, 很显然得到 m == 13 二进制末尾 1 的位置是 2 的 0 次方位, 将 13 - 0001 == 12, 再对 12 执行 lowbit 操作, 1100 & 0100 == 0100, 也很轻易得到了 m == 12 时二进制末尾 1 的位置是 2 的 2 次方位, 将 12 - 0100 == 8, 再对 8 执行 lowbit 操作, 0100 & 1100 == 0100, 得到 m == 8 时二进制位是 2 的 2 次方位, 8 - 0100 == 0(结束操作), 通过循环得到的 13,12,8, 则 sum(13) == C13 + C12 + C8
求前缀和的代码
- int ans = 0;
- int getSum(int m){
- while(m> 0){
- ans += C[m];
- m -= lowbit(m);
- }
- }
对于 n 次前缀和的查询, 时间复杂度为 O(nlogn)
接下来讲解单点更新值
对于输入编号为 x 的值, 要求为它的值附加一个 value 值, 我们把图再一次拿下来
假设 x==2,value==5, 那么我们先找到 A[2]的位置, 通过观察我们得知, 如果修改了 A[2]的值, 那么管辖 A[2]的 C[2],C[4],C[8]的前缀和都要加上 value(所有的祖先节点), 那么和查询类似, 我们如何得到 C2 的所有祖先节点呢 (因为 C2 和 A2 的下标相同所以更新时查询从 C[x] 开始), 依旧是上述的巧妙的方法, 但是我们把它倒过来
对于要更新 x 位置的值, 我们把 x 转换成二进制, 不断对二进制最后一个 1 的位置 + 1, 直到达到数组下标的最大值 n 结束
对于给出的例子 x==2, 假设数组下标上限 n==8,x 转换成二进制后等于 0010(C2), 对末尾 1 的位置进行 + 1, 得到 0100(C4), 对末尾的 1 的位置进行 + 1, 得到 1000(C8), 循环结束, 对 C2,C4,C8 的前缀和都要加上 value, 当然不能忘记对 A[2]的值 + value, 单点更新值过程结束
给出代码
- void update(int x, int value){
- A[x] += value; // 不能忘了对 A 数组进行维护, 尽善尽美嘛
- while(x <= n){
- C[x] += value;
- x += lowbit(x);
- }
- }
对于 n 次更新操作, 时间复杂度同样为 O(nlogn)
这里有一个注意事项, 我们对于求前缀和与单点更新时, 树状数组 C 是拿来直接使用的, 那么问题来了, 树什么时候建立好的, 我怎么不知道??
事实上, 对于一个输入的数组 A, 我们一次读取的过程, 就可以想成是一个不断更新值的过程 (把 A1~An 从 0 更新成我们输入的 A[i]), 所以一边读入 A[i], 一边将 C[i] 涉及到的祖先节点值更新, 完成输入后树状数组 C 也就建立成功了
完整代码如下:
- #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){ // 用于测试 n == 8
- memset(a, 0, sizeof(a));
- memset(c, 0, sizeof(c));
- for(int i = 1; i <= n; i++){
- scanf("%d", &a[i]); //a[i]的值根据具体题目自己安排测试可以 1,2,3,4,5,6,7,8
- update(i, a[i]); // 输入的过程就是更新的过程
- }
- int ans = getSum(n-1); // 用于测试输出 n-1 的前缀和 输出 28
- printf("%d\n", ans);
- }
- return 0;
- }
posted on 2019-08-01 11:54 乌克兰大野猪 阅读(...) 评论(...) 编辑 收藏
来源: https://www.cnblogs.com/findview/p/11281628.html