首页 > 代码库 > 树状数组
树状数组
树状数组（Binary Indexed Tree(BIT), Fenwick Tree） 是一个查询和修改的复杂度都为 log(n) 的数据结构。
观察下图：
令这棵树的结点编号为 C?1??,C?2??,…,C?n??。令每个结点的值为这棵树的值的总和，那么容易发现：
C?1??=A?1??
C?2??=A?1??+A?2??
C?3??=A?3??
C?4??=A?1??+A?2??+A?3??+A?4??
C?5??=A?5??
C?6??=A?5??+A?6??
C?7??=A?7??
C?8??=A?1??+A?2??+A?3??+A?4??+A?5??+A?6??+A?7??+A?8??
…
C?16??=A?1??+A?2??+A?3??+A?4??+A?5??+A?6??+A?7??+A?8??+A?9??+A?10??+A?11??+A?12??+A?13??+A?14??+A?15??+A?16??
有一个有趣的性质：
设结点编号为 x，那么该结点区间为 2^k??（其中 k 为 x 二进制末尾 0 的个数）个元素。
因为这个区间最后一个元素必然为 A?x??，
所以很明显，
计算这个 2^k??，也就是最低位的 1，可以这样写：
int lowbit(int x) {
return x & (x ^ (x – 1));
}
利用机器补码特性，也可以写成：
int lowbit(int x) {
return x & -x;
}
查询
当想要查询一个 sum(1…n) 即 (a?1??+a?2??+…+a?n??)，可以依据如下算法即可：
step 1: 令 sum = 0，转第二步；
step 2: 假如 n≤0，算法结束，返回 sum 值，否则 sum = sum + Cn，转第三步；
step 3: 令 n = n - lowbit(n)，转第二步。
可以看出，这个算法就是将这一个个区间的和全部加起来，为什么是效率是 log(n) 的呢？
证明：
n = n - lowbit(n)等价于将 n 的二进制的最后一个 1 减去。而 n 的二进制里最多有 og(n) 个 1，所以查询效率是 log(n) 的。
int getsum(int x) {
int res = 0;
for (; x; x -= x & (-x))
res += t[x];
return res;
}
修改
step 1：当 i > n 时，算法结束，否则转第二步；
step 2：Ci = Ci + x, i = i + lowbit(i) 转第一步。
i = i + lowbit(i) 这个过程实际上也只是一个把末尾 1 补为 0 的过程。
修改一个节点，必须修改其所有祖先，最坏情况下为修改第一个元素，最多有 log(n) 个祖先。
int change(int x) {
for (; x <= maxn; x += x & (-x))
t[x]++;
}
树状数组