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)
对于节点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 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
|