08月04, 2018

了解树状数组

简介

树状数组(Binary Indexed Tree)字面意思就是二叉索引树,他不需要开辟额外的空间来建树,只是在原序列进行操作,多用于 统计区间和 和 更新单点的值,操作的时间复杂度均为log(N)。

建树

树?or数组?怎样结合?

树状数组独特的建树方式,以下标为索引抽象出来一棵树,假设现在需要维护这样一个数组int a[11] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10},如下图: alt

仔细观察上图可以发现一个规律,将所有下标转化成二进制,每个下标的父节点就是右边末尾连续0个数比自己多的最近的一个下标。有一点绕,举个例子,5转化成二进制为101,末尾连续0的个数为0,6转化成二进制为110,末尾连续0的个数为1,刚好比5多一个,并且举例5最近,所以下标6作为下标5的父节点。

找到建树方法之后,怎样确定本节点的父节点?

第一个比自己大并且第一个末尾0个数比自己多的数,如果想要构造这样一个数,转化成最终问题,就是找到自己二进制从lowbit开始的第一个1的位置,然后这个位置+1,就得到想要的数,也就是自己的父节点。

举个例子,6的二进制为110,如果6减去1,那么值变为5也就是101,也就是说减一操作,一直影响从lowbit开始到第一个为1的位(取反),那么 n XOR (n – 1)得出来的数就是n从lowbit开始到第一位为1的位全部为1,剩下的位为0,然后用n XOR (n – 1)的值与n做AND操作,得到末尾第一个1的位置,请看下图:

alt

还有另一种方式x AND –x得到末尾第一个1的位置,利用了计算机补码的特性,这里不做展开。

查询:

树状数组每个节点维护以当前节点为根节点子树的权值和,要查询[a, b]区间内的权值和时,一般用[1, b]区间减去[1, a – 1]区间。

获取[1, x]区间权值和:

将目的转化一下就变成,将[1, x]区间内每棵孤立树根节点的权值相加。找到一个根节点就把权值加到累加器中,然后寻找下一个根节点,方案:

alt

统计[1, 6]区间和,那么原本的树就变成上图这样,右端点一定是最后单棵树的根节点(因为他左边的只能是他儿子),这样得到第一个根节点,然后去寻找下一个根节点,下个根节点是下标6左边第一个末尾0比6的末尾0个数多的下标,找到6从lowbit起第一个1的位置,将这一位值0,就得到下一个根节点。

代码实现:

#include <bits/stdc++.h>

#define MAXN 123456
#define BEGIN 1
#define END 10
#define lowbit(x) (x & (-x))

using namespace std;

int c[MAXN];

// 更新下标为x处的值
void update(int x, int val) {
   while (x < MAXN) {
      c[x] += val;
      x += lowbit(x);
   }  
}

// 获取[1, x]区间内的权值和
int getsum(int x) {
   int res = 0;
   while (x > 0) {
      res += c[x];
      x -= lowbit(x);
   }
   return res;
}

int main() {   
   // 建树
   for (int i = BEGIN; i <= END; i ++) {
      update(i, i);
   }
   // 查询
   for (int i = BEGIN; i <= END; i ++) {
      for (int j = i; j <= END; j ++) {
         // 查询区间[i, j]的权值和
         printf("The sum from %d to %d : %d\n", i, j, getsum(j) - getsum(i - 1));
      }
   }  
   return 0;
}

本文链接:https://www.opsdev.cn/post/BinaryIndexedTree.html

-- EOF --

Comments

评论加载中...

注:如果长时间无法加载,请针对 disq.us | disquscdn.com | disqus.com 启用代理。