樹狀陣列 Fenwick Tree — lowbit 原理與前綴和查詢完整實作 | 資料結構與演算法

2026/06/27
javascript 資料結構&演算法 Fenwick Tree 樹狀陣列 BIT
樹狀陣列 Fenwick Tree — lowbit 原理與前綴和查詢完整實作 | 資料結構與演算法

樹狀陣列（Fenwick Tree，又稱 Binary Indexed Tree，簡稱 BIT） 是一種利用二進位表示中最低位元（lowbit）巧妙設計索引的資料結構，能以 O(log n) 時間同時支援單點更新與前綴和查詢。相較於 線段樹，BIT 程式碼極為精簡（核心不超過 10 行），常數因子更小，是處理前綴和動態維護與逆序對計數問題的首選工具。

前言

想像你在管理一個遊戲排行榜，玩家分數隨時更新，你需要快速回答：「有多少人的分數在 1000 到 5000 之間？」

如果分數範圍是 [1, 10000]，每次查詢都從頭掃描是 O(n)，1000 次查詢就慢得難以接受。靜態前綴和能讓查詢達到 O(1)，但每次更新都必須重建整個陣列。

樹狀陣列（BIT） 用一個極其巧妙的索引技巧，讓更新和查詢都穩定在 O(log n)，核心程式碼不超過 10 行，卻藏著深刻的二進位數學原理。

學習本文後你將能夠：

  • 理解 lowbit 運算的數學原理（二補數）
  • 掌握 BIT 節點管轄區間的設計邏輯
  • 用 TypeScript 與 C++ 實作完整的 BIT 類別
  • 處理區間更新、逆序對計數、2D BIT 等進階應用
  • 在面試與競程中判斷何時該用 BIT、何時改用線段樹

核心概念：lowbit 運算

lowbit 是什麼

BIT 的一切都建立在一個只有一行的函式上：

const lowbit = (x: number): number => x & (-x);

lowbit(x) 取出 x 的二進位表示中最低位的 1，傳回它代表的值。

為什麼 x & (-x) 能取出最低位 1

利用二補數（Two’s Complement） 的性質：

  • -x 等於 ~x + 1（取反後加 1）
  • 取反後，x 的最低位 1 變成 0，加 1 後這個 0 進位，重新變回 1
  • 然而更高位元全部翻轉，因此 x & (-x) 只保留最低位的 1
x  =  6  → 二進位: 0 1 1 0
-x = -6  → 二進位: 1 0 1 0  （補數）
x & (-x) = 0 0 1 0 = 2  ← 最低位 1

x  = 12  → 二進位: 1 1 0 0
-x = -12 → 二進位: 0 1 0 0
x & (-x) = 0 1 0 0 = 4  ← 最低位 1

BIT 節點管轄的區間

BIT 的節點 i 負責管理從 i - lowbit(i) + 1 到 i 的原始元素之和：

i = 1 → lowbit=1 → 管理 [1, 1]
i = 2 → lowbit=2 → 管理 [1, 2]
i = 3 → lowbit=1 → 管理 [3, 3]
i = 4 → lowbit=4 → 管理 [1, 4]
i = 5 → lowbit=1 → 管理 [5, 5]
i = 6 → lowbit=2 → 管理 [5, 6]
i = 7 → lowbit=1 → 管理 [7, 7]
i = 8 → lowbit=8 → 管理 [1, 8]

這個設計讓 BIT 隱含了一棵樹形結構：

                 bit[8]          ← [1,8]
                /      \
           bit[4]      bit[6]    bit[7]
           /    \       /
       bit[2]  bit[3] bit[5]
       /
    bit[1]

前綴和查詢：向左跳

查詢 sum[1..i]：從 i 出發，不斷減去 lowbit(i)，沿途累加所有 BIT 節點值，直到 i 歸零為止。

query(6):
  bit[6] 管理 [5,6]  → 加入 bit[6]，i = 6 - lowbit(6) = 6 - 2 = 4
  bit[4] 管理 [1,4]  → 加入 bit[4]，i = 4 - lowbit(4) = 4 - 4 = 0
  停止

sum[1..6] = bit[4] + bit[6]

最多跳 O(log n) 步，因為每步至少清掉一個二進位位元。

單點更新：向右跳

更新位置 i 的值：從 i 出發，不斷加上 lowbit(i)，更新所有涵蓋 i 的 BIT 節點。

update(3, Δ):
  bit[3] 管理 [3,3]  → 更新 bit[3]，i = 3 + lowbit(3) = 3 + 1 = 4
  bit[4] 管理 [1,4]  → 更新 bit[4]，i = 4 + lowbit(4) = 4 + 4 = 8
  bit[8] 管理 [1,8]  → 更新 bit[8]，i = 8 + 8 = 16 > n，停止

JavaScript/TypeScript 實作

基礎 BIT（單點更新 + 前綴和查詢）

class BIT {
  private n: number;
  private tree: number[];

  constructor(n: number) {
    this.n = n;
    this.tree = new Array(n + 1).fill(0);
  }

  // 從陣列初始化，O(n log n)
  static fromArray(nums: number[]): BIT {
    const bit = new BIT(nums.length);
    for (let i = 0; i < nums.length; i++) {
      bit.update(i + 1, nums[i]); // BIT 使用 1-indexed
    }
    return bit;
  }

  // O(n) 建樹（利用 parent 關係，比逐一 update 快）
  static fromArrayFast(nums: number[]): BIT {
    const n = nums.length;
    const bit = new BIT(n);
    for (let i = 1; i <= n; i++) {
      bit.tree[i] += nums[i - 1];
      const parent = i + (i & -i);
      if (parent <= n) bit.tree[parent] += bit.tree[i];
    }
    return bit;
  }

  // 單點更新：在 index（1-indexed）處加上 delta
  update(index: number, delta: number): void {
    for (; index <= this.n; index += index & -index) {
      this.tree[index] += delta;
    }
  }

  // 前綴和查詢：sum[1..index]
  query(index: number): number {
    let sum = 0;
    for (; index > 0; index -= index & -index) {
      sum += this.tree[index];
    }
    return sum;
  }

  // 區間查詢：sum[l..r]（1-indexed）
  rangeQuery(l: number, r: number): number {
    return this.query(r) - this.query(l - 1);
  }

  // 單點查詢：獲取 index 處的當前值
  pointQuery(index: number): number {
    return this.rangeQuery(index, index);
  }
}

// 使用範例
const bit = BIT.fromArray([1, 3, 5, 7, 9, 11]);
console.log(bit.rangeQuery(2, 4)); // 輸出：15 (3+5+7)
bit.update(3, 2);                   // index=3 加 2，值從 5 變成 7
console.log(bit.rangeQuery(2, 4)); // 輸出：17 (3+7+7)

差分 BIT（區間更新 + 單點查詢）

透過維護差分陣列，可以讓 BIT 支援區間加法更新：

// 概念：維護差分陣列 D，D[i] = A[i] - A[i-1]
// 區間 [l,r] 加 v → D[l]+=v, D[r+1]-=v
// 查詢 A[i] = D[1]+D[2]+...+D[i] = prefix(D, i)
class DiffBIT {
  private bit: BIT;
  private n: number;

  constructor(n: number) {
    this.n = n;
    this.bit = new BIT(n);
  }

  // 區間 [l, r] 所有元素加 val
  rangeAdd(l: number, r: number, val: number): void {
    this.bit.update(l, val);
    if (r + 1 <= this.n) this.bit.update(r + 1, -val);
  }

  // 查詢 index 處的當前值（經過所有區間更新後）
  pointQuery(index: number): number {
    return this.bit.query(index);
  }
}

區間更新 + 區間查詢（雙 BIT）

利用恆等式，可以同時支援區間更新與區間查詢：

// 公式推導：
// prefix_sum(A, r) = sum_{i=1}^{r} A[i]
//                 = (r+1) * sum(D[i]) - sum(D[i] * i)
// 因此維護兩個 BIT：bit1 存 D[i]，bit2 存 D[i]*i
class RangeUpdateRangeQuery {
  private bit1: number[]; // 儲存 D[i]
  private bit2: number[]; // 儲存 D[i] * i
  private n: number;

  constructor(n: number) {
    this.n = n;
    this.bit1 = new Array(n + 2).fill(0);
    this.bit2 = new Array(n + 2).fill(0);
  }

  private add(bit: number[], i: number, val: number): void {
    for (; i <= this.n; i += i & -i) bit[i] += val;
  }

  private sum(bit: number[], i: number): number {
    let s = 0;
    for (; i > 0; i -= i & -i) s += bit[i];
    return s;
  }

  private prefixSum(i: number): number {
    return (i + 1) * this.sum(this.bit1, i) - this.sum(this.bit2, i);
  }

  // 區間 [l, r] 加 val
  rangeAdd(l: number, r: number, val: number): void {
    this.add(this.bit1, l, val);
    this.add(this.bit1, r + 1, -val);
    this.add(this.bit2, l, val * l);
    this.add(this.bit2, r + 1, -val * (r + 1));
  }

  // 區間 [l, r] 求和
  rangeQuery(l: number, r: number): number {
    return this.prefixSum(r) - this.prefixSum(l - 1);
  }
}

二維 BIT（2D BIT）

二維 BIT 的時間複雜度為 O(log m × log n)，空間 O(mn)：

class BIT2D {
  private tree: number[][];
  private rows: number;
  private cols: number;

  constructor(rows: number, cols: number) {
    this.rows = rows;
    this.cols = cols;
    this.tree = Array.from(
      { length: rows + 1 },
      () => new Array(cols + 1).fill(0)
    );
  }

  // 單點更新：(r, c) 加 delta（1-indexed）
  update(r: number, c: number, delta: number): void {
    for (let i = r; i <= this.rows; i += i & -i) {
      for (let j = c; j <= this.cols; j += j & -j) {
        this.tree[i][j] += delta;
      }
    }
  }

  // 前綴矩形和：sum[(1,1)..(r,c)]
  query(r: number, c: number): number {
    let sum = 0;
    for (let i = r; i > 0; i -= i & -i) {
      for (let j = c; j > 0; j -= j & -j) {
        sum += this.tree[i][j];
      }
    }
    return sum;
  }

  // 子矩形和：sum[(r1,c1)..(r2,c2)]（容斥原理）
  rangeQuery(r1: number, c1: number, r2: number, c2: number): number {
    return (
      this.query(r2, c2) -
      this.query(r1 - 1, c2) -
      this.query(r2, c1 - 1) +
      this.query(r1 - 1, c1 - 1)
    );
  }
}

C++ 對照實作

基礎 BIT

#include <bits/stdc++.h>
using namespace std;

struct BIT {
    int n;
    vector<long long> tree;

    BIT(int n) : n(n), tree(n + 1, 0) {}

    // O(n) 建樹
    BIT(const vector<int>& nums) : n(nums.size()), tree(nums.size() + 1, 0) {
        for (int i = 1; i <= n; i++) {
            tree[i] += nums[i - 1];
            int parent = i + (i & -i);
            if (parent <= n) tree[parent] += tree[i];
        }
    }

    // 單點更新：index (1-indexed) 加 delta
    void update(int i, long long delta) {
        for (; i <= n; i += i & -i)
            tree[i] += delta;
    }

    // 前綴和查詢 sum[1..i]
    long long query(int i) const {
        long long sum = 0;
        for (; i > 0; i -= i & -i)
            sum += tree[i];
        return sum;
    }

    // 區間查詢 sum[l..r]
    long long query(int l, int r) const {
        return query(r) - query(l - 1);
    }
};

int main() {
    vector<int> nums = {1, 3, 5, 7, 9, 11};
    BIT bit(nums);
    cout << bit.query(2, 4) << "\n"; // 輸出：15
    bit.update(3, 2);
    cout << bit.query(2, 4) << "\n"; // 輸出：17
    return 0;
}

區間更新 + 區間查詢（雙 BIT）

struct RangeUpdateBIT {
    int n;
    vector<long long> bit1, bit2; // bit1: D[i], bit2: D[i]*i

    RangeUpdateBIT(int n) : n(n), bit1(n + 2, 0), bit2(n + 2, 0) {}

    void add(vector<long long>& bit, int i, long long v) {
        for (; i <= n; i += i & -i) bit[i] += v;
    }

    long long sum(const vector<long long>& bit, int i) const {
        long long s = 0;
        for (; i > 0; i -= i & -i) s += bit[i];
        return s;
    }

    long long prefixSum(int i) const {
        return (i + 1) * sum(bit1, i) - sum(bit2, i);
    }

    void rangeAdd(int l, int r, long long val) {
        add(bit1, l, val);
        add(bit1, r + 1, -val);
        add(bit2, l, val * l);
        add(bit2, r + 1, -val * (r + 1));
    }

    long long rangeQuery(int l, int r) const {
        return prefixSum(r) - prefixSum(l - 1);
    }
};

複雜度分析：BIT vs 線段樹

維度BIT（樹狀陣列）線段樹
程式碼複雜度低（10-20 行）高（50-150 行）
時間常數較小（簡單迴圈）較大（多次遞迴）
空間複雜度O(n)O(4n)
單點更新O(log n)O(log n)
前綴和查詢O(log n)O(log n)
區間查詢（任意）O(log n)O(log n)
區間更新（加法）O(log n)（差分）O(log n)（懶標記）
區間最大/最小值不支援原生支援
區間賦值困難支援（懶標記）
持久化不原生支援支援（主席樹）
二維版本簡單支援支援（複雜）
適用場景前綴和/逆序對複雜區間操作

決策準則：若問題只需要「單點更新 + 前綴和查詢」或「逆序對計數」，優先選 BIT。若需要「區間最大/最小」、「區間賦值」或「持久化」，必須使用線段樹。

變體與延伸

在 BIT 上進行二分搜尋

由於 BIT 的結構本質是二元樹，可以在 BIT 上直接進行 O(log n) 的第 K 大元素查詢，無需額外排序。這種技巧稱為 Binary Lifting on BIT：

// 在 BIT 上找第 k 個 1 的位置（bit[i] 存 0 或 1，查詢第 k 個 1 在哪）
findKth(k: number): number {
  let pos = 0;
  let bitMask = 1 << Math.floor(Math.log2(this.n));
  while (bitMask > 0) {
    const next = pos + bitMask;
    if (next <= this.n && this.tree[next] < k) {
      pos = next;
      k -= this.tree[next];
    }
    bitMask >>= 1;
  }
  return pos + 1;
}

離散化配合 BIT

當值域過大時（例如 nums[i] 可達 10^9），需先把值域壓縮到 [1, m]（m 為不同值的數量），才能用 BIT：

function discretize(nums: number[]): Map<number, number> {
  const sorted = [...new Set(nums)].sort((a, b) => a - b);
  const rank = new Map<number, number>();
  sorted.forEach((v, i) => rank.set(v, i + 1));
  return rank;
}

多維 BIT

三維 BIT 的時間複雜度為 O(log³ n) 每次操作，空間 O(n³)。實際應用中超過二維通常改用動態開點線段樹或 KD-Tree 以控制空間消耗。

面試考點：逆序對計數

逆序對（Inversion）是 BIT 最經典的面試應用，核心思路是「從左往右掃描，對每個元素查詢目前已插入中有多少個比它大」。

離散化 + BIT 計算逆序對

function countInversions(nums: number[]): number {
  const n = nums.length;

  // 離散化：將值壓縮到 [1, m]
  const sorted = [...new Set(nums)].sort((a, b) => a - b);
  const rank = new Map<number, number>();
  sorted.forEach((v, i) => rank.set(v, i + 1));
  const m = sorted.length;

  const bit = new BIT(m);
  let inversions = 0;

  // 從左往右掃描
  // 對於 nums[i]，逆序對數 = 已插入元素中比 nums[i] 大的個數
  //                         = 已插入數量 - prefix(rank[nums[i]])
  for (let i = 0; i < n; i++) {
    const r = rank.get(nums[i])!;
    inversions += i - bit.query(r); // 已插入 i 個，其中 prefix(r) 個 <= nums[i]
    bit.update(r, 1);
  }

  return inversions;
}

// 測試
console.log(countInversions([3, 1, 2]));    // 輸出：2 (對: (3,1), (3,2))
console.log(countInversions([5, 4, 3, 2, 1])); // 輸出：10

區間和查詢

靜態前綴和 O(1) 查詢但不支援更新；BIT 讓更新也達到 O(log n)，是動態場景的最佳選擇：

// 動態維護區間和 — LeetCode 307 BIT 解法
class NumArray {
  private bit: number[];
  private nums: number[];
  private n: number;

  constructor(nums: number[]) {
    this.n = nums.length;
    this.nums = [...nums];
    this.bit = new Array(this.n + 1).fill(0);
    // O(n) 建樹
    for (let i = 1; i <= this.n; i++) {
      this.bit[i] += nums[i - 1];
      const parent = i + (i & -i);
      if (parent <= this.n) this.bit[parent] += this.bit[i];
    }
  }

  update(index: number, val: number): void {
    const delta = val - this.nums[index];
    this.nums[index] = val;
    // BIT 是 1-indexed
    for (let i = index + 1; i <= this.n; i += i & -i) {
      this.bit[i] += delta;
    }
  }

  sumRange(left: number, right: number): number {
    return this.prefix(right + 1) - this.prefix(left);
  }

  private prefix(i: number): number {
    let sum = 0;
    for (; i > 0; i -= i & -i) sum += this.bit[i];
    return sum;
  }
}

// 複雜度：建樹 O(n)，更新 O(log n)，查詢 O(log n)，空間 O(n)

LeetCode 練習題

LeetCode 307 — Range Sum Query Mutable（Medium）

題意：支援單點更新和區間求和查詢。

思路：直接套用基礎 BIT。注意 LeetCode 使用 0-indexed，呼叫 BIT 時需 +1 轉換。

複雜度：建樹 O(n)，更新與查詢均 O(log n)。

LeetCode 315 — Count of Smaller Numbers After Self（Hard）

題意：對每個 nums[i]，計算其右側有多少個元素嚴格小於它。

思路：從右往左掃描，對每個 nums[i] 先查詢 BIT 中 [1, rank-1] 的計數，再插入自己。

function countSmaller(nums: number[]): number[] {
  const n = nums.length;

  // 離散化
  const sorted = [...new Set(nums)].sort((a, b) => a - b);
  const rank = new Map<number, number>();
  sorted.forEach((v, i) => rank.set(v, i + 1));
  const m = sorted.length;

  // BIT：值域 [1, m]
  const bit = new Array(m + 1).fill(0);

  const update = (i: number): void => {
    for (; i <= m; i += i & -i) bit[i]++;
  };

  const query = (i: number): number => {
    let sum = 0;
    for (; i > 0; i -= i & -i) sum += bit[i];
    return sum;
  };

  const result: number[] = new Array(n);
  for (let i = n - 1; i >= 0; i--) {
    const r = rank.get(nums[i])!;
    result[i] = query(r - 1); // 比自己小的個數（值域 [1, r-1]）
    update(r);                 // 插入自己
  }
  return result;
}

// 複雜度：O(n log n)，空間 O(n)

LeetCode 493 — Reverse Pairs（Hard）

題意：計算陣列中滿足 nums[i] > 2 * nums[j] 且 i < j 的對數。

思路：與逆序對類似，但條件是 > 2 * nums[j] 而非 > nums[j]，因此需要分開進行「查詢」與「插入」，避免計入自身。同樣需要離散化，注意查詢的值域是 > 2 * nums[j]。

複雜度：O(n log n)，空間 O(n)。

LeetCode 327 — Count of Range Sum（Hard）

題意：計算有多少個子陣列的區間和落在 [lower, upper] 之間。

思路：先算前綴和 prefix[i]，問題轉化為計算有多少對 (i, j) 滿足 lower <= prefix[j] - prefix[i] <= upper。離散化前綴和後，從左到右掃描，對每個 prefix[j] 查詢 BIT 中 [prefix[j]-upper, prefix[j]-lower] 的計數。

複雜度：O(n log n)，空間 O(n)。

LeetCode 1649 — Create Sorted Array through Instructions（Hard）

題意：按順序插入元素，每次插入的代價是 min(已插入中比自己小的個數, 已插入中比自己大的個數)，求總代價。

思路：BIT 維護已插入元素的頻率，對每個新元素查詢左側計數與右側計數，取小值累加。

複雜度：O(n log C)（C 為值域大小），空間 O(C)。

常見陷阱

  1. 0-indexed vs 1-indexed 混淆：BIT 必須使用 1-indexed（從 1 開始）。索引 0 在 BIT 中無意義，0 & -0 = 0 會導致無限迴圈。若原始陣列是 0-indexed，呼叫時需加 1 轉換。

  2. 忘記儲存原始值進行單點更新：BIT 的 update 是差分更新（加上 delta），若題目要求「設定某點為新值」，需先儲存原始值計算 delta = newVal - oldVal，再呼叫 update(i, delta)。

  3. 初始建樹方法選擇不當：呼叫 n 次 update 建樹是 O(n log n)，利用 parent 累加的 O(n) 建樹更高效。但 O(n) 建樹的寫法需特別注意：tree[i] += nums[i-1] 後，再把 tree[i] 傳給 parent，而非把 nums[i-1] 傳給 parent。

  4. 二維 BIT 邊界條件：二維 BIT 的 query(0, c) 和 query(r, 0) 應返回 0，迴圈條件 i > 0 和 j > 0 已保證正確。常見錯誤是在 rangeQuery 中誤用 query(r1, c1) 而非 query(r1-1, c1-1) 導致容斥計算錯誤。

  5. 離散化後 BIT 值域設定錯誤：若離散化後有 m 個不同值，BIT 的大小應為 m+1（1-indexed 需多一個空間）。查詢「比自己嚴格小」時，應查詢 query(rank - 1)，而非 query(rank)（後者會包含等於自己的元素）。

總結

樹狀陣列（BIT） 是競程與面試中最值得掌握的資料結構之一，原因在於它的代價與收益極度不成比例：核心只有 10 行程式碼，卻能解決前綴和動態維護、逆序對計數、排名查詢等一整類問題。

本文涵蓋的核心知識點：

  • lowbit 運算：x & (-x) 利用二補數取出最低位 1，決定 BIT 節點管轄的區間長度
  • 查詢與更新：查詢向左跳（i -= lowbit(i)），更新向右跳（i += lowbit(i)），各 O(log n)
  • 進階變體：差分 BIT 支援區間加法更新、雙 BIT 支援區間更新+區間查詢、2D BIT 支援矩形區間查詢
  • 決策框架：前綴和 + 單點更新 → BIT；區間最大/最小/賦值/持久化 → 線段樹

掌握 BIT 之後，建議練習以下 LeetCode 題目鞏固概念：307（基礎），315、493（離散化逆序對），327、1649（進階應用）。

希望這篇文章能幫助你徹底理解樹狀陣列的設計精妙之處，並在需要動態前綴和的問題上信手拈來。如有任何問題或疑惑，歡迎在下方留言交流！

下一篇預告：我們將進入進階樹結構，探討 線段樹進階應用 與其他樹形資料結構，敬請期待！

← 上一篇：線段樹 — Lazy Propagation 與區間查詢完整實作
BenZ Software Developer

熱愛技術的軟體開發者，在這裡分享程式開發經驗與學習筆記。