深圳南山住房和建设局网站,成都十大猎头公司,网站 经营性,网站搜索引擎一、简介树状数组 (Binary Indexed Tree,BIT)#xff0c;利用数的二进制特征进行检索的一种树状结构。一种真正的高级数据结构#xff1a; 二分思想、二叉树、位运算、前缀和。高效!代码极其简洁!二、基本应用数列a1,a2,....,an#xff0c;操作#xff1a;单点修改#xf…一、简介树状数组 (Binary Indexed Tree,BIT)利用数的二进制特征进行检索的一种树状结构。一种真正的高级数据结构 二分思想、二叉树、位运算、前缀和。高效!代码极其简洁!二、基本应用数列a1,a2,....,an操作单点修改修改元素add(k,x) 把ak加上x。求和sum (x) a1 ... ax区间和ai ... aj sum(j) - sum(i-1)三、不修改、只查询数列aj, a2,..., an求区间和 ai ...aj数列是静态的用前缀和计算区间和特别高效。前缀和sum[i]a1... ai区间和 ai...aj sum[j]-sum[i-1]查询一次区间和O(1)代码如果数列是动态的修改元素add(k,x)把a加上x。复杂度O(1)求区间和sum(j) - sum(i-1)复杂度O(n)---------效率低四、动态修改、求区间和 用树状数组数列是动态的修改元素add(k,x)把ak加上x。求区间和sum(j) - sum(i-1)复杂度都是 O(logn)代码五、从二叉树到树状数组六、神奇的lowbit(x)操作语法lowbit(x)x -x功能找到x的二进制数的最后一个1七、tree[ ]数组从lowbit(x)推出tree[ ]数组所有的计算都基于tree[ ]令m lowbit(x)。定义tree[x]把ax和它前面共m个数相加。例 lowbit(6)2有tree[6] a5a6。横线中的黑色表示tree[x]等于横线上元素相加的和。八、基于tree[ ]的计算求和suma1 ...ax利用tree[ ]数组求sum例如sum[8] tree[8]sum[7] tree[7] tree[6] tree[4]sum[9] tree[9] tree[8]以上关系是如何得到的?借助lowbit(x)。九、sum[ ]的计算例 sum[7] tree[7] tree[6] tree[4](1)从7开始加上tree[7](2) 7 -lowbit(7) 6加上tree[6](3) 6 - lowbit(6) 4加上tree[4](4) 4-lowbit(4) 0结束。sum()的复杂度?---------O(logn)------非常好!十、sum[ ]的更新更改ax和它相关的tree都会变化。例如改变a3那么tree[3]、tree[4]、tree[8]...都会改变。影响哪些tree[ ]? 仍然利用lowbit(x)(1) 更改tree[3](2) 3 lowbit(3) 4更改tree[4](3) 4 lowbit(4)8更改tree[8](4)直到最后的tree[n]。复杂度?---------O(logn)------非常好!
