算法笔记 - 树状数组 （Fenwick tree）

功能描述

对于一个长度为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可以使用树状数组实现