树状数组

1. 树状数组原理

1.1 核心思想

树状数组利用二进制分解将前缀和分解为 $O(\log n)$ 个区间的和：

$\text{prefix}(i) = \sum_{j=1}^{i} a[j] = \text{tree}[i] + \text{tree}[i - \text{lowbit}(i)] + \ldots$

1.2 lowbit 运算

lowbit(x) 返回 x 二进制最低位的 1 所代表的值：

$\text{lowbit}(x) = x \ \& \ (-x)$

x = 6  = 0110 → lowbit = 0010 = 2
x = 12 = 1100 → lowbit = 0100 = 4
x = 7  = 0111 → lowbit = 0001 = 1
x = 8  = 1000 → lowbit = 1000 = 8

1.3 树形结构

数组: [1, 3, 5, 7, 9, 11, 13, 15]

tree[1] = a[1]                           = 1
tree[2] = a[1] + a[2]                    = 4
tree[3] = a[3]                           = 5
tree[4] = a[1] + a[2] + a[3] + a[4]     = 16
tree[5] = a[5]                           = 9
tree[6] = a[5] + a[6]                    = 20
tree[7] = a[7]                           = 13
tree[8] = a[1]+...+a[8]                  = 64

每个 tree[i] 管辖 [i-lowbit(i)+1, i] 的区间

2. 基本操作

2.1 单点更新

class FenwickTree:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)

    def update(self, i, delta):
        """在位置 i 加上 delta"""
        while i <= self.n:
            self.tree[i] += delta
            i += i & (-i)  # i += lowbit(i)

2.2 前缀查询

    def query(self, i):
        """查询 [1, i] 的和"""
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & (-i)  # i -= lowbit(i)
        return s

    def range_query(self, l, r):
        """查询 [l, r] 的和"""
        return self.query(r) - self.query(l - 1)

2.3 操作流程示意

update(3, +5):
  tree[3] += 5   (3 → 3+lowbit(3)=4)
  tree[4] += 5   (4 → 4+lowbit(4)=8)
  tree[8] += 5   (8 → 8+lowbit(8)=16 > n, 停止)

query(7):
  tree[7]        (7 → 7-lowbit(7)=6)
  + tree[6]      (6 → 6-lowbit(6)=4)
  + tree[4]      (4 → 4-lowbit(4)=0, 停止)

3. 差分数组扩展

3.1 区间修改 + 单点查询

利用差分数组的树状数组：

class FenwickDiff:
    def __init__(self, n):
        self.ft = FenwickTree(n)

    def range_add(self, l, r, delta):
        """区间 [l, r] 加 delta"""
        self.ft.update(l, delta)
        self.ft.update(r + 1, -delta)

    def point_query(self, i):
        """查询位置 i 的值"""
        return self.ft.query(i)

3.2 区间修改 + 区间查询

使用两个树状数组：

class FenwickRange:
    def __init__(self, n):
        self.n = n
        self.t1 = [0] * (n + 1)  # 差分值
        self.t2 = [0] * (n + 1)  # 差分值 × 位置

    def _update(self, tree, i, val):
        while i <= self.n:
            tree[i] += val
            i += i & (-i)

    def _query(self, tree, i):
        s = 0
        while i > 0:
            s += tree[i]
            i -= i & (-i)
        return s

    def range_add(self, l, r, val):
        self._update(self.t1, l, val)
        self._update(self.t1, r + 1, -val)
        self._update(self.t2, l, val * (l - 1))
        self._update(self.t2, r + 1, -val * r)

    def range_query(self, l, r):
        def prefix_sum(i):
            return self._query(self.t1, i) * i - self._query(self.t2, i)
        return prefix_sum(r) - prefix_sum(l - 1)

4. 经典应用

4.1 逆序对计数

def count_inversions(arr):
    # 离散化
    sorted_vals = sorted(set(arr))
    rank = {v: i + 1 for i, v in enumerate(sorted_vals)}

    ft = FenwickTree(len(sorted_vals))
    inversions = 0
    for i in range(len(arr) - 1, -1, -1):
        r = rank[arr[i]]
        inversions += ft.query(r - 1)  # 比当前值小的已出现个数
        ft.update(r, 1)
    return inversions

4.2 离散化技巧

当值域很大但数据稀疏时，先离散化再建树：

def discretize(arr):
    sorted_unique = sorted(set(arr))
    return {v: i + 1 for i, v in enumerate(sorted_unique)}

5. 与线段树对比

选择建议：单点更新+区间查询用树状数组，区间修改用线段树。