首页 > 代码库 > 树状数组
树状数组
树状数组(Binary Indexed Tree(BIT), Fenwick Tree)是一个查询和修改复杂度都为log(n)的数据结构。主要用于查询任意两位之间的所有元素之和，但是每次只能修改一个元素的值；
经过简单修改可 以在log(n)的复杂度下进行范围修改，但是这时只能查询其中一个元素的值(如果加入多个辅助数组则可以实现区间修改与区间查询)。其实现如下：
int lowbit(int pos){ return pos&(-pos); ／／找出最后的１，并计算出低位有１的值，如６，二进制为１１０，则求出为１０， }
／／由下面的规律可得，树状数组在相应位置会累计数据void add(int pos, int value){ while(pos < c.size()){ c[pos] += value; pos += lowbit(pos); }
}
／／求和的时候由于在相应位置有累积数据，需跳跃int sum(int pos){ int res = 0; while(pos > 0){ res += c[pos]; pos -= lowbit(pos); } return res;}
树状数组以４为周期，找规律如下：
C1 = A1
C2 = A1 + A2
C3 = A3
C4 = A1 + A2 + A3 + A4
C5 = A5
C6 = A5 + A6
C7 = A7
C8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8
...
C16 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8 + A9 + A10 + A11 + A12 + A13 + A14 + A15 + A16
树状图可能看起来会更直观
Range Sum Query - Mutable
leetcode中的一个题目
树状数组
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。