树状数组

2023-08-06

树状数组，也称为二进制索引树，是一种支持单点更新和区间查询的数据结构。在大多数情况下，我们可以用它来查询区间和、区间乘积或其他满足以下条件的操作：

结合律：
具有逆运算，我们可以通过和推断出

它基于这样一个假设：任何前缀都可以分解为最多个区间，这些区间的信息是已知的。

从上图可以看出，每个位置控制的区间的右边界是。在树状数组中，被分配控制长度为的区间。这里，是从右边数第一个 1 位的位置减 1。例如，$12 = (1100)2 $，则$ k = 2 $，$ 2^k = 4 $。所以在这种情况下，$ c{12} $控制的区间是$ [12 - 4 + 1, 12] $。$ 2^k $可以使用函数获得，即$ x\ & \ (-x)$。

def lowbit(x):
    return x & (-x)


# 单点更新
def update_ft(ft, index, val):
    diff = val - ft[index]
    while index <= len(ft) - 1:
        ft[index] += diff
        index += lowbit(index)


def create_ft(arr):
    n = len(arr)
    ft = [0] * (n + 1)
    for i in range(1, n + 1):
        update_ft(ft, i, arr[i - 1])


def get_sum(ft, end):
    ret = 0
    while end > 0:
        ret += ft[end]
        end -= lowbit(end)
    return ret