【NOIp复习】数据结构之树状数组

树状数组的功能

以O(log(N))的复杂度实现区间求和、单点修改以O(log(N))的复杂度实现单点查询、区间修改

实现方法

lowbit函数

取出一个二进制数的最末尾1 例如：lowbit(10010100)=100

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

原理分析（直观）

末尾0的个数代表了该数组在树上的深度（从下往上） 比如100末尾有两个0，它就等于10\11\100三个节点的和 1000末尾有3个0，它就等于100\110\111\1000四个节点的和

在求前缀和时不难发现，从右下往左上依次累加，直到仅最高位为0的区间（即包含第一个元素）为止观察节点编号不难发现，节点n的父节点为n+lowbit(n)

有了以上两点结论就可以编写树状数组的查询和修改操作了。

int Sum(int end){ int sum=0; while(end>0){ sum+=C[end]; end-=lowbit(end); } return sum; } void Add(int pos,int num){ while(pos<=n){ C[pos]+=num; pos+=lowbit(pos); } return; }

转载于:https://www.cnblogs.com/leotan0321/p/6081410.html