首页 > 代码库 > 树状数组
树状数组
基本概念
树状数组(Binary Indexed Tree(BIT), Fenwick Tree)是一个查询和修改复杂度都为log(n)的数据结构。主要用于查询任意两位之间的所有元素之和,但是每次只能修改一个元素的值;经过简单修改可以在log(n)的复杂度下进行范围修改,但是这时只能查询其中一个元素的值。
假设数组A[1..n], 用C[i]表示A[i-2k +1]到A[i]的和,而k则是i在二进制时末尾0的个数,或者说是i用2的幂方和表示时的最小指数。当然,利用位运算,我们可以直接计算出2k=i and (i xor (i-1)) 或 i and (-i);
树状数组C,其中C[i]=a[i-2k+1]+……+a[i](k为i在二进制形式下末尾0的个数)。由c数组的定义可以得出:
c[1]=a[1]
c[2]=a[1]+a[2]=c[1]+a[2]
c[3]=a[3]
c[4]=a[1]+a[2]+a[3]+a[4]=c[2]+c[3]+a[4]
c[5]=a[5]
c[6]=a[5]+a[6]=c[5]+a[6]
……
1.求最小幂2^k
int lowbit(int n){ return n&(n^(n-1)); }也可以写成:
int lowbit(int n){ return n&(-n); }
2.对某个元素进行加法操作:将a[p]的值加上一个值x(x可正可负);
//向上更新 void ADD(int p, int val){ while(p<=maxn){ //maxn是给定上限 c[p] += val; p += lowbit(p); } }
3.当想要查询一个sum(n)(a[0]~a[n]的值)
int getsum(int p){ int sum = 0; while(p>0){ sum += c[p]; p -= lowbit(p); } return sum; }
Mark一下:
HDU-1556 http://acm.hdu.edu.cn/showproblem.php?pid=1556
HDU-1166 http://acm.hdu.edu.cn/showproblem.php?pid=1166
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。