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

功能描述

对于一个长度为N数组array

在 $O(logN)$ 的时间复杂度下，统计出从第一个元素开始区间和，也就是 $sum(1,x)$ ，
给数组中一个元素增加一个值 $V$ ，时间复杂度 $O(logN)$
空间复杂度 $O(N)$
实现特别简单

注意事项

没有办法直接算出区间和，需要通过换算 $sum(i, j) = sum(j) - sum(i-1)$ , 时间复杂度还是 $O(logN)$
方便直接给位置增加一个特定值，但是修改查询单个数值比较复杂。
无法区间修改，不能实现线段树的RMQ功能
区间和的时间复杂度比传统线段树要低，实现更加简单
效率和zkw线段树差不多，所以现在这个算法使用很少了

算法的结构

image.png

函数lowbit在树状数组中操作的说明

lowbit函数的作用是找到数字二进制的最后一个数字1。举例

$x_{10}$	$x_{2}$	$lowbit(x)_{2}$	$lowbit(x)_{10}$
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数值 的作用，是找到最近的父亲节点。在修改点 $P_{5}$ 的数值是，父亲的寻找过程是：

第一个父亲的下标是是 $5_{10} + lowbit(5_{10}) = 101_{2} + 1_2 = 110_{2} = 6_{10}$
第二个父亲是下标是 $6_{10} + lowbit(6_{10}) = 110_{2} + 10_2 = 1000_2 = 8_{10}$
第三个父亲的下标（如果有）是 $16_{10} + lowbit(16_{10}) = 32_{10}$
直到计算出来的下标，超过了数组的范围，就计算完成了。

减去lowbit的数值的作用，是找到每一个需要被统计的子树的根节点。是上图红色标志的路线。对于 $sum(1, 11)$ 的数值，分别有三个子树需要被计算进来

第一个需要收集的子树是 sum( 11, 11 ) , 因为 $lowbit(11_{10})= lowbit( 1011_2 ) = 1_2$ ，这个子树只有一个数，就是 $11_{10}$
第二个需要收集的子树覆盖宽度，是 $lowbit(11_{10} - 1_{10}) = lowbit(10_{10}) = lowbit(1010_2) = 10_2 = 2_{10}$ , 也就是，有两个元素，也就是 $sum(9, 10)$
以此类推，第三个子树是 $sum(1, 8)$ 。这时候统计完毕， $sum(1, 11) = tree[8] + tree[10] + tree[11]$

示范代码

C语言实现，来自维基百科。但是这里我修改了一点点，size放大了1，更方便理解。数值的存储是 $[1, SIZE]$

#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可以使用树状数组实现

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