一、算法概述

树状数组（Fenwick Tree / Binary Indexed Tree, BIT） 是一种支持单点修改和前缀和查询的高效数据结构。它利用二进制中最低位 1（lowbit）将线性数组组织成树状结构，在 O(log n) 时间内完成更新和查询操作。

相比线段树，树状数组实现更简单、常数更小、空间更省，但功能略有限制（通常仅支持可逆运算，如加法/异或）。

二、核心思想

2.1 lowbit 操作

定义 lowbit(x) = x & (-x)，它返回 x 的二进制表示中最低位的 1 所代表的值。

例如：

  • lowbit(6) = lowbit(110₂) = 2（最低位 1 在第 1 位，值为 2¹ = 2）
  • lowbit(8) = lowbit(1000₂) = 8
  • lowbit(7) = lowbit(111₂) = 1

2.2 树状数组结构

树状数组 tree[i] 管理的区间为 [i - lowbit(i) + 1, i]，长度为 lowbit(i)。

tree[1] 管理 [1, 1]       lowbit(1)=1
tree[2] 管理 [1, 2]       lowbit(2)=2
tree[3] 管理 [3, 3]       lowbit(3)=1
tree[4] 管理 [1, 4]       lowbit(4)=4
tree[5] 管理 [5, 5]       lowbit(5)=1
tree[6] 管理 [5, 6]       lowbit(6)=2
tree[7] 管理 [7, 7]       lowbit(7)=1
tree[8] 管理 [1, 8]       lowbit(8)=8

2.3 操作原理

单点更新 add(i, delta)： 要将 arr[i] 增加 delta，需要更新所有覆盖了位置 i 的 tree 节点。这些节点的下标为：i, i + lowbit(i), i + lowbit(i) + lowbit(i + lowbit(i)), ... 直到超出范围。

前缀和查询 sum(i)： 要查询 arr[1] + ... + arr[i]，需要累加所有不重叠的 tree 节点。从 i 开始，每次减去 lowbit(i)，将这些节点的值加起来。

区间查询 rangeSum(l, r)：利用前缀和性质：sum(r) - sum(l - 1)。

区间更新 + 单点查询（差分思想）：用树状数组维护差分数组，区间加 [l, r] + delta 转化为 add(l, delta) 和 add(r+1, -delta)。

三、算法步骤 / 伪代码

lowbit

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

单点更新

function add(index, delta):
    while index <= N:
        tree[index] = tree[index] + delta
        index = index + lowbit(index)

前缀和查询

function sum(index):
    result = 0
    while index > 0:
        result = result + tree[index]
        index = index - lowbit(index)
    return result

区间查询

function rangeSum(L, R):
    return sum(R) - sum(L - 1)

区间修改（差分 BIT）

function rangeAdd(L, R, delta):
    add(L, delta)
    add(R + 1, -delta)

四、C++ 代码实现

#include <iostream>
#include <vector>
using namespace std;

class FenwickTree {
private:
    vector<int> tree;
    int n;

    int lowbit(int x) {
        return x & (-x);
    }

public:
    // 构造函数：初始化大小为 n+1（1-indexed）
    FenwickTree(int size) : n(size), tree(size + 1, 0) {}

    // 用初始数组构建树状数组 O(n log n)
    FenwickTree(const vector<int>& arr) {
        n = arr.size();
        tree.resize(n + 1, 0);
        for (int i = 0; i < n; i++) {
            add(i + 1, arr[i]);  // 1-indexed
        }
    }

    // ========== 单点更新：给位置 index 加上 delta ==========
    void add(int index, int delta) {
        while (index <= n) {
            tree[index] += delta;
            index += lowbit(index);
        }
    }

    // ========== 前缀和查询：查询 [1, index] 的和 ==========
    int prefixSum(int index) {
        int result = 0;
        while (index > 0) {
            result += tree[index];
            index -= lowbit(index);
        }
        return result;
    }

    // ========== 区间查询：[L, R] 的和 ==========
    int rangeSum(int L, int R) {
        return prefixSum(R) - prefixSum(L - 1);
    }
};

// ==================== 差分树状数组：支持区间修改 + 单点查询 ====================
class DiffFenwickTree {
private:
    vector<int> diff;
    int n;

    int lowbit(int x) {
        return x & (-x);
    }

public:
    DiffFenwickTree(int size) : n(size), diff(size + 2, 0) {}  // 多开一位防止 r+1 越界

    void add(int index, int delta) {
        while (index <= n + 1) {
            diff[index] += delta;
            index += lowbit(index);
        }
    }

    // 区间 [L, R] 全部加上 delta
    void rangeAdd(int L, int R, int delta) {
        add(L, delta);
        add(R + 1, -delta);
    }

    // 单点查询位置 index 的值
    int pointQuery(int index) {
        int result = 0;
        while (index > 0) {
            result += diff[index];
            index -= lowbit(index);
        }
        return result;
    }
};

// ==================== 测试主函数 ====================
int main() {
    // 测试1：基本功能
    cout << "===== 测试1：单点更新 + 区间查询 =====" << endl;
    vector<int> arr = {1, 3, 5, 7, 9, 11};
    FenwickTree bit(arr);

    cout << "初始数组: ";
    for (int v : arr) cout << v << " ";
    cout << endl;

    cout << "前缀和 sum(3) = " << bit.prefixSum(3) << " (期望: 9)" << endl;
    cout << "区间和 [2, 5] = " << bit.rangeSum(2, 5) << " (期望: 24)" << endl;

    // 单点更新
    bit.add(3, 10);  // arr[3] 增加 10 => 5 -> 15
    cout << "\n执行 add(3, 10) 后:" << endl;
    cout << "前缀和 sum(3) = " << bit.prefixSum(3) << " (期望: 19)" << endl;
    cout << "区间和 [2, 5] = " << bit.rangeSum(2, 5) << " (期望: 34)" << endl;
    cout << "区间和 [1, 6] = " << bit.rangeSum(1, 6) << " (期望: 46)" << endl;

    // 测试2：差分 BIT——区间修改 + 单点查询
    cout << "\n===== 测试2：区间修改 + 单点查询 =====" << endl;
    DiffFenwickTree diffBit(6);
    // 初始全0
    cout << "初始全0，查询各点: ";
    for (int i = 1; i <= 6; i++) {
        cout << diffBit.pointQuery(i) << " ";
    }
    cout << endl;

    // 区间 [2, 4] 加上 5
    diffBit.rangeAdd(2, 4, 5);
    cout << "执行 rangeAdd(2, 4, 5) 后: ";
    for (int i = 1; i <= 6; i++) {
        cout << diffBit.pointQuery(i) << " ";
    }
    cout << "\n期望: 0 5 5 5 0 0" << endl;

    // 区间 [3, 6] 加上 3
    diffBit.rangeAdd(3, 6, 3);
    cout << "执行 rangeAdd(3, 6, 3) 后: ";
    for (int i = 1; i <= 6; i++) {
        cout << diffBit.pointQuery(i) << " ";
    }
    cout << "\n期望: 0 5 8 8 3 3" << endl;

    // 测试3：逆序对计数（经典应用）
    cout << "\n===== 测试3：用树状数组统计逆序对 =====" << endl;
    vector<int> nums = {5, 3, 2, 4, 1};
    FenwickTree bit2(10);  // 值域 1~10
    int reversePairs = 0;
    for (int x : nums) {
        // 查询比 x 大的数有多少个已经出现过
        reversePairs += bit2.rangeSum(x + 1, 10);
        bit2.add(x, 1);
    }
    cout << "数组 [5, 3, 2, 4, 1] 的逆序对数量: " << reversePairs << " (期望: 9)" << endl;

    return 0;
}

五、复杂度分析

操作 时间复杂度 说明
单点更新 add O(log n) 每次跳跃 lowbit，最多 log n 次
前缀和查询 prefixSum
区间查询 rangeSum 两次前缀和查询
建树（逐个插入） O(n log n) n 次 add 操作
建树（线性建树） O(n) 利用前缀和思想优化
空间复杂度 仅需一个大小为 n+1 的数组
  • 单次操作 O(log n)：lowbit 跳跃每次至少将最低位 1 消除（查询）或进位（更新），跳跃次数不超过二进制位数
  • 常数极小：操作仅为几个位运算和数组访问，实际运行速度非常快
  • 空间 O(n)：仅存储一个长度为 n+1 的数组，远优于线段树的 4n

六、应用场景

场景 说明
动态维护前缀和 数组元素频繁修改，需要快速查询区间和
逆序对计数 值域较小时，用 BIT 统计已出现元素中比当前元素大的数量
区间修改 + 单点查询 使用差分 BIT 实现
区间修改 + 区间查询 维护两个 BIT（经典公式推导）
求第 K 小元素 在 BIT 上二分查找前缀和（倍增法）
二维偏序 / 三维偏序 CDQ 分治配合 BIT 解决偏序问题
LIS（最长上升子序列） 优化 DP 转移，O(n log n)

七、经典例题

LeetCode 307 - 区域和检索 - 数组可修改

题目：给定一个整数数组 nums，实现以下操作：

  • update(index, val)：将 nums[index] 更新为 val
  • sumRange(left, right)：返回 nums[left] 到 nums[right] 的和（包含两端）

解题思路：直接用树状数组维护。update 操作需计算差值 delta = val - nums[index]，然后调用 add(index+1, delta)。

// LeetCode 307 核心代码片段
class NumArray {
    FenwickTree bit;
    vector<int> nums;
public:
    NumArray(vector<int>& nums) : bit(nums), nums(nums) {}
    
    void update(int index, int val) {
        int delta = val - nums[index];
        nums[index] = val;
        bit.add(index + 1, delta);
    }
    
    int sumRange(int left, int right) {
        return bit.rangeSum(left + 1, right + 1);
    }
};

进一步练习：

  • LeetCode 315：计算右侧小于当前元素的个数（逆序对变形）
  • LeetCode 327：区间和的个数（前缀和离散化 + BIT）
  • LeetCode 493：翻转对（归并 / BIT）
  1. Language
  2. 兼容模式
  3. 主题
  3. Worker 0, 14ms
  4. Powered by Hydro v5.0.1 Community