目录
一、介绍
树状数组（Binary Indexed Tree，BIT），又称为 Fenwick 树，是一种高效的数据结构，主要用于动态维护数组的前缀和（或区间和），以及支持单点更新的操作。其核心思想是利用二进制的特性，通过巧妙地设计数据结构，对每一部分设置了一个“管理员”，管理员存储量其管理对象的所和，从而实现快速的区间查询和单点更新操作。因此当需要对前n和数据进行求和的时候就不需要遍历n次，只需要查询对应管理员中的数值即可。
本篇仅仅介绍一维的树状数组，多维的原理和此是一样的。
二、一维树状数组
这里需要了解几个关于树状数组的几个定义。
首先我们定义一个管理数组，也就是上面提到的“管理员”。管理员的个数和一维数组的元素个数相同。
再定义所有存储的一维数组为。
2.1 区间长度
这里的区间长度指的是每一个管理员所管理的具体对象的多少。对于，若
的二进制末尾有k个连续的0，则
存储的区间长度为
，即从
向前数
个元素的累加和。例如，6的二级制为110，末尾有1个0，区间长度为2，就存储了
，即
。
得到二进制末尾连续0的个数的方法是，将该二进制数取反后加一，再与原值做与运算。例如：20的二进制为10100，是原始二进制数，取反后为01011，加1后为01100，此时最低位的1和原数最低位的1的位置是一样的，01100和10100做与运算就得到了00100
取反
&
得到的区间长度为4。这里定义函数得到的是区间的长度。
2.2 前驱和后继
直接的前驱为
直接的后继为
前驱：的直接前驱，直接前驱的直接前驱...
后继：的直接后继，直接后继的直接后继...
2.3 查询前缀和
前个元素的前缀和
等于
加上
的前驱。例如
为
加上
的前驱。而
的前驱为
，且
没有前驱，故
。
解释一下的前驱。i=5，其二进制为0101，末尾没有0，故区间长度为1（2的0次方），则其前驱为
，同理可得
没有前驱，故只有一个前驱。
2.4 点更新
若对进行了修改，加上了z，则只需要更新
以及后继即可，让所有的都加上z。因为该更新只会改变其本身和后继的数值，对前驱是没有影响的。
需要注意的是，树状数组的下标需要从1开始，否则会出现死循环。
三、一维数组的实现
3.1 区间长度函数
在计算机中，使用二进制的补码进行表示刚好是 取反加1，因此
int lowbit(int i)
{
return (-i) & i; //计算区间区间的大小
}3.2 前缀和
int sum(int i)
{
int s = 0;
for (; i > 0; i -= lowbit(i))
{
s += c[i];
}
return s;
}3.3 插入/更新
该函数可以用来更新数值，也可以用来创建树状数组。只要把初始化为0，
遍历
插入即可。
void add(int i, int z)
{
for (; i <= 9; i += lowbit(i))
{
c[i] += z;
}3.4 封装成类
class BITree
{
private:
std::vector<int> c; //存储树的节点和
int size; //数组的大小
int lowbit(int i); //计算区间的大小
public:
BITree(int n); //输入数据量
void Update(int i, int z); //修改数据
int sum(int i); //查询
};
BITree::BITree(int n)
{
size = n;
c.resize(n + 1, 0);
}
int BITree::lowbit(int i)
{
return (-i) & i;
}
void BITree::Update(int i, int z)
{
for (; i <= 9; i += lowbit(i))
{
c[i] += z;
}
}
int BITree::sum(int i)
{
int s = 0;
for (; i > 0; i -= lowbit(i))
{
s += c[i];
}
return s;
}测试：
int main()
{
int a[9] = { 1,2,3,4,5,6,7,8,9 };
for (int i = 0; i < 9; i++)
{
add(i + 1, a[i]);
}
std::cout << sum(9) << std::endl;
BITree tree(9);
for (int i = 0; i < 9; i++)
{
tree.Update(i + 1, a[i]);
}
std::cout << tree.sum(4) << std::endl;
return 0;
}
