功能描述
对于一个长度为N数组array
- 在
的时间复杂度下，统计出从第一个元素开始区间和，也就是
，
- 给数组中一个元素增加一个值
，时间复杂度
- 空间复杂度
- 实现特别简单
注意事项
- 没有办法直接算出区间和，需要通过换算
, 时间复杂度还是
- 方便直接给位置增加一个特定值，但是修改查询单个数值比较复杂。
- 无法区间修改，不能实现线段树的RMQ功能
- 区间和的时间复杂度比传统线段树要低，实现更加简单
- 效率和zkw线段树差不多，所以现在这个算法使用很少了
算法的结构
image.png
函数lowbit在树状数组中操作的说明
lowbit函数的作用是找到数字二进制的最后一个数字1。举例
| 5 | 101 | 1 | 1 |
| 6 | 110 | 10 | 2 |
| 10 | 1010 | 10 | 2 |
| 20 | 10100 | 100 | 4 |
| 22 | 10110 | 10 | 2 |
| 27 | 11011 | 1 | 1 |
路径图
加上lowbit数值 的作用，是找到最近的父亲节点。在修改点 的数值是，父亲的寻找过程是：
- 第一个父亲的下标是是
- 第二个父亲是下标是
- 第三个父亲的下标（如果有）是
- 直到计算出来的下标，超过了数组的范围，就计算完成了。
减去lowbit的数值的作用，是找到每一个需要被统计的子树的根节点。 是上图红色标志的路线。对于的数值，分别有三个子树需要被计算进来
- 第一个需要收集的子树是 sum( 11, 11 ) , 因为
， 这个子树只有一个数，就是
- 第二个需要收集的子树覆盖宽度，是
, 也就是，有两个元素，也就是
- 以此类推， 第三个子树是
。 这时候统计完毕，
示范代码
C语言实现，来自维基百科。但是这里我修改了一点点，size放大了1， 更方便理解。数值的存储是
#define LSB(i) ((i) & -(i)) // zeroes all the bits except the least significant one
int A[SIZE+1];
int sum(int i) // Returns the sum from index 1 to i
{
int sum = 0;
while (i > 0)
sum += A[i], i -= LSB(i);
return sum;
}
void add(int i, int k) // Adds k to element with index i
{
while (i <=SIZE)
A[i] += k, i += LSB(i);
}
题目
leetcode 的 683 - k-empty-slots可以使用树状数组实现
