Binary indexed tree

2018/02/27 11:44
阅读数 97

Fenwick tree

它又叫 Binary indexed tree ,也叫树状数组。

能在log(n)查询区间和,并且在log(n)时间内进行结点更新操作。

 

 

lowbit(x)函数

定义lowbit(x)为x的二进制表达式中最右边的1所对应的值。

比如,1234的二进制是0100 1101 0010  lowbit(1234)=2,在程序的实现中,

Lowbit(x)=x&-x;(为什么这样写呢?因为计算机内部采用补码表示,-x是x按位取反,尾数+1的结果)

 

树的结构图

让我们来看看图:横坐标是x, 纵坐标是lowbit(x)

fenwick_tree_binary_index_tree

对于节点x,

  • 为左子结点,则父结点的编号是x+lowbit(x),
  • 为右子结点,则父结点的编号是x-lowbit(x)

设C[i] 为以i结尾的水平长条内的元素之和,如c[6]=a5+a6。

  • 顺着结点I往左走,边走边往上爬,沿途经过的c[i]所对应的长条不重复不遗漏的包含了所有需要累加的元素。
    • 如sum(6) = c[6] + c[4]
  • 如果修改了一个a[i] ,那么从c[i]往右走,边走边网上爬,沿途修改所有结点对应的c[i]即可。
    • 如a[1] + 1 那么 c[1] + 1, c[2]+1,c[4]+1………一直到最大值。

用C++ 的代码如下:

inline int lowbit(int x) { return x&(-x) ; }
 
int sum(int x)            
{ 
    int ans=0; 
    while(x>0)        
    {        
        ans+=C[x]; 
       x-=lowbit(x); 
    } 
    return ans; 
} 
 
void add(int x,int d) 
{ 
    while(x<=N) 
    { 
        C[x]+=d; 
       x+=lowbit(x); 
    } 
} 

 

 

 

实现代码

写成类的话:

C++

 

 
class FenwickTree {
	vector<int> sum_array;
	int n;
	inline int lowbit(int x) {
		return x & -x;
	}

public:
	FenwickTree(int n) :n(n), sum_array(n + 1, 0) {}

	void add(int x, int val) {
		while (x <= n) {
			sum_array[x] += val;
			x += lowbit(x);
		}
	}

	int sum(int x) {
		int res = 0;
		while (x > 0) {
			res += sum_array[x];
			x -= lowbit(x);
		}
		return res;
	}
};

 

 

Python

 

class FenwickTree(object):
    def __init__(self, n):
        self.sum_array = [0] * (n + 1)
        self.n = n

    def lowbit(self, x):
        return x & -x

    def add(self, x, val):
        while x <= self.n:
            self.sum_array[x] += val
            x += self.lowbit(x)

    def sum(self, x):
        res = 0
        while x > 0:
            res += self.sum_array[x]
            x -= self.lowbit(x)
        return res

 

 

 

 

 

展开阅读全文
加载中

作者的其它热门文章

打赏
0
0 收藏
分享
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部