Fenwick tree

2018/08/09 ALGO

A Fenwick tree or binary indexed tree is a data structure that can efficiently update elements and calculate prefix sums in a table of numbers. This structure was proposed by Peter Fenwick in 1994 to improve the efficiency of arithmetic coding compression algorithms.

When compared with a flat array of numbers, the Fenwick tree achieves a much better balance between two operations: element update and prefix sum calculation. In a flat array of n numbers, you can either store the elements, or the prefix sums. In the first case, computing prefix sums requires linear time; in the second case, updating the array elements requires linear time (in both cases, the other operation can be performed in constant time). Fenwick trees allow both operations to be performed in O(log n) time. This is achieved by representing the numbers as a tree, where the value of each node is the sum of the numbers in that subtree. The tree structure allows operations to be performed using only O(log n) node accesses.

算法分析

Fenwick tree 或者 binary indexed tree,称作树状数组,它是一种数据结构,用于高效处理对存储数字的列表进行更新、求前缀和的数据结构。树状数组K保存着对数组Ans特定的数据,可以在O(log n)的时间内计算数组Ans的前缀和。

继续阅读之前,强调两个数组:一个是原始数组Ans,另一个是树状数组K。其中,K的生成是依赖Ans的。

常见的,树状数组具备三个高效操作:

  1. update:数组Ans的某一位元素更新的时候,快速更新树状数组K。

  2. prefixSum:通过树状数组K来计算数组Ans中前n个元素的和。

  3. rangeSum:通过树状数组K来计算数组Ans中位置a到位置b之间的和。

问题思考

树状数组解决的问题是快速求解区间的和。那么传统的方法是如何求解区间的和呢?例如给定一个数组Ans,计算Ans[5]到Ans[4653]之间的所有数字的和,我们需要使用一个for循环来遍历序号5到序号4653的元素,总共循环4648次。

树状数组的方法是通过创建等长的树状数组K,来保存下某种特殊的数据,使得我们在统计区间的和能够将时间降低到log n次,因此这是一种很典型的时空算法。我们通过牺牲空间来换取时间的减少。在计算机中,显然时间的重要性比空间的重要性大。

树状数组的结构是如何

lowbit函数

在学习树状数组结构之前,我们先了解一个lowbit函数。lowbit函数的主要工作是计算出整数x的二进制表达中从右到左第一个出现1的数值。例如,lowbit(6) = 2,原因是6的二进制是110,那么从右到左第一个出现的1的值是10,也就是2。例如,lowbit(64) = 64,原因是64的二进制是1000000,那么从右到左第一个出现的1的值就是它自己本身,因此结果是64。

下面的lowbit函数的C实现。

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

在C/C++语言里面,&符号是按位与,也就是当两个二进制都为1的时候结果为1,其余情况为0。上面的代码是如何做到满足lowbit函数的要求呢?

先补充一个知识点。计算机中的符号数有3种表达方式,分别是原码、补码、反码。其中符号位0表示正数,1表示负数。计算机系统中,保存一个数使用补码的形式。一个数n的原码是1个符号位 + n的二进制表达,n的反码是1个符号位 + n的二进制表达的相反位,而n的补码则分几种情况讨论:

  1. 如果n是正数,那么n的补码就是其原码。

  2. 如果n是负数,那么n的补码就是其反码加1。

  3. 0的补码是全0。

例如:

数字9, 二进制是0001001。
原码是00001001
反码是01110110
补码是00001001(等于原码)

数字-5,二进制是0000101。
原码是10000101
反码是11111010
补码是11111011(反码+1)

有一个口诀,假如计算机中某个整数x,将其每一个位(包含符号位)取反之后再加1,得到的新的值是x的相反数。简称取反加一。

下面我们来证明lowbit函数做了什么:

假设整数x的格式是 …..10…0,其中出现的1是从右到左数的第一个1,此时1右边有可能有0,有可能没有0。那么,-x的格式便是……10…0,也就是1右边依旧是保持不变,但是1的左边已经全部取反了。因此x与-x进行按位与的时候,1的左右边都全为0了。例如:

x = 2788
它的二进制表达是101011100100
计算机中保存的补码是0101011100100
那么-x在计算机中的表达是1010100011100

0101011100100
1010100011100
-------------
0000000000100

因此按位与的结果与lowbit函数的要求是一致的

树状数组的结构

再强调两个数组,一个是原始数组Ans,另一个是树状数组K。其中,K的生成是依赖Ans的。这两个数组都是从1开始数起,并且等长。

其中,数组K的第i个元素表示数组Ans从第i个元素(包含自己)向前数lowbit(i)个元素的和。例如:

  1. K[1] = Ans[1]
  2. K[2] = Ans[2] + Ans[1]
  3. K[3] = Ans[3]
  4. K[4] = Ans[4] + Ans[3] + Ans[2] + Ans[1]

以此类推。下面两个图形象的表达出数组K与数组Ans的关系:

更新树状数组

当数组Ans的某一个位置发生变化的时候,我们需要同时更新树状数组K,否则上面的结构就会不成立了。更新的时候,本质上是更新包含当前位置以及后续影响的幂次方的位。语言上的描述有点难以理解,用图例来观察:

例如,当Ans[3]的元素增加3,那么K[3]本身需要更新,K[4]、K[8]、…、K[2^n]都需要更新为添加3。

因此,update操作可以描述为:

void update(int index, int value){
    // len是数组K的长度
    while(index <= len){
        K[index] += value;
        index += lowbit(index);
    }
}

也可以简写为:

void update(int index, int value){
    for(;index <= len;c[index] += value, index += lowbit(index));
}

这个操作的复杂度是O(log n)。

查询树状数组

注意,树状数组K的定义中容易混淆认为K[i]是Ans前i个元素的和,这是不正确的。数组K的第i个元素表示数组Ans从第i个元素(包含自己)向前数lowbit(i)个元素的和。例如查询计算Ans[1]到Ans[7]的和:

计算Ans[1]到Ans[7]的和可以计算K[7] + K[6] + K[4]得到。下面是对树状数组查询的表达:

int sum(int index){
    // len是数组K的长度
    int result = 0;
    while(index){
        result += K[index];
        index -= lowbit(index);
    }
    return result;
}

这个操作的复杂度是O(log n)。

计算区间和

假如我现在需要计算出Ans数组中位置a到位置b的和,那么该如何处理呢?如果用函数表达,则为:

int p_sum(int a, int b){
    return sum(b) - sum(a) + Ans[a];
}

这个操作的复杂度是O(log n)。

POJ 2481

Farmer John’s cows have discovered that the clover growing along the ridge of the hill (which we can think of as a one-dimensional number line) in his field is particularly good.

Farmer John has N cows (we number the cows from 1 to N). Each of Farmer John’s N cows has a range of clover that she particularly likes (these ranges might overlap). The ranges are defined by a closed interval [S,E].

But some cows are strong and some are weak. Given two cows: cow i and cow j, their favourite clover range is [Si, Ei] and [Sj, Ej]. If Si <= Sj and Ej <= Ei and Ei - Si > Ej - Sj, we say that cow i is stronger than cow j.

For each cow, how many cows are stronger than her? Farmer John needs your help!

题目的意思是,给定n个区间[S, E],对于每一个区间求出能够覆盖自身的区间的数量。

解题的思路是使用树状数组。首先对n组区间进行排序,其中按E从大到小排序,如果E相等,则S从小到大排序。排序之后的结果cow[n],保证了能够覆盖cow[i]的区间只可能出现在前i个元素。为什么呢?假如某个区间j,满足j < i,那么这个cow[j].E >= cow[i].E,如果相等,那么cow[j].S <= cow[i].S,那么这个区间j很有可能覆盖区间i。

那么对于这个已经排序好的cow[n],问题就转化为,cow[n]中按顺序遍历第i个区间,在cow[1]直到cow[i](再强调,答案只可能出现在i之前)中满足cow[???].S <= cow[i].S的数量是多少呢?

那么抽象出一个数组Ans,其中Ans[i]表示区间左界为i的区间数量。那么问题再转变为计算Ans[1]到Ans[S]的和。这个时候我就可以使用树状数组K了,每一次遍历cow[n],就更新数组K状态+1,因为新添加的这个区间对应的S位置,Ans[S]增加1。这样就可以通过树状数组K来快速查询这个和是多少。

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

int cas=1,T;
int cnt[100100];
int ans[100010];

struct node{
	int s,e,index;
}cow[100010];

int n;
int lowbit(int x){
	return x&(-x);
}
int sum(int x){
	int ans=0;
	while(x>0){
		ans+=cnt[x];
		x-=lowbit(x);
	}
	return ans;
}
void add(int x,int v){
	while (x<=100010){
		cnt[x]+=v;
		x+=lowbit(x);
	}
}
bool cmp(node a,node b){
    if(a.e!=b.e)
	    return a.e>b.e;
    return a.s<b.s;
}

int main(){
	while(scanf("%d",&n)!=EOF && n){
		memset(ans,0,sizeof(ans));
		memset(cnt,0,sizeof(cnt));
		for(int i=0;i<n;i++){
			scanf("%d%d",&cow[i].s,&cow[i].e);
			cow[i].s++;
			cow[i].e++;
			cow[i].index=i;
		}
		sort(cow,cow+n,cmp);
	    ans[cow[0].index]=sum(cow[0].s);
		add(cow[0].s,1);
		for(int i=1;i<n;i++){
			if (cow[i].s==cow[i-1].s && cow[i].e==cow[i-1].e)
				ans[cow[i].index]=ans[cow[i-1].index];
			else
				ans[cow[i].index]=sum(cow[i].s);
			add(cow[i].s,1);
		}
		for (int i=0;i<n-1;i++)
			printf("%d ",ans[i]);
		printf("%d\n",ans[n-1]);
	}
	return 0;
}

Search

    Table of Contents