樹狀數組原理與實現：用二叉樹視角徹底理解Fenwick Tree

編輯：關於C語言

樹狀數組（Binary Indexed Tree, BIT / Fenwick Tree）以O(log n)支援點更新區間查詢或區間更新點查詢，是競賽編程與工程高頻數據結構。傳統解釋依賴lowbit位運算，直觀性差。本文通過中序遍歷二叉樹視角，從結構本質推導操作邏輯，讓你一眼看穿能做什麼、不能做什麼。

一、二叉樹視角的直觀模型

對大小為N的數組，構建完全二叉樹，葉子節點對應數組下標1..N，內部節點通過中序遍歷編號1..N。每個內部節點只統計左子樹葉子的信息。

BIT二叉樹模型

關鍵性質（可證）

葉子k一定在節點k的左子樹下。
節點k的左子樹葉子數 = lowbit(k) = k & (-k)（二進制最低位1）。
節點k統計區間：(k - lowbit(k), k]。
父節點：k + lowbit(k)（在右子樹）、k - lowbit(k)（在左子樹）。
左孩子：k - lowbit(k)/2。

二、兩種基本操作模式

定義兩個父節點集合：

up_right(k)：k在其左子樹的所有祖先（沿k + lowbit(k)向上）。
up_left(k)：k在其右子樹的所有祖先（沿k - lowbit(k)向上）。

模式 1：點更新、區間查詢 [1, y]（標準BIT）

更新 x：訪問 x 及所有 up_right(x)，加上 delta。
查詢 [1, y]：將 [1, y] 拆解為不重疊區間 → 訪問 y 及所有 up_left(y)，累加求和。

模式 2：區間更新 [1, y]、點查詢 x（差分BIT）

節點存儲「該區間所有葉子共同增加了多少」。
更新 [1, y]：訪問 y 及 up_left(y)。
查詢 x：訪問 x 及 up_right(x)。

兩模式互為對偶，本質相同。

三、局限性：為什麼不能任意區間最值？

BIT 只統計左子樹（或右子樹）聚合信息。任意區間[x, y]的信息無法由[1, x-1]與[1, y]的聚合信息反推（最值、最大公約數等不可逆運算）。
結論：BIT 適用於可逆聚合（求和、異或、計數），不適用於不可逆聚合（最值、最小公倍數）。

四、空間與定位效率

空間：N+1（下標從1開始），比線段樹4N省記憶體。
定位父/子節點：位運算O(1)，比線段樹指標/數組下標計算更快。
自上而下查找第k小：從最高二進制位遞減試探，O(log N)（見代碼erase_nth）。

五、完整 C++ 模板實現（含逆序數、約瑟夫環）


template <int Total, typename T = int>
class BIT {
    enum { Min2k = Round2k<Total>::down };  // 最大2的冪
    T info[Total + 1];
    T sz;  // 當前總計數

    int lowbit(int x) { return x & -x; }
    void left_up(int &x) { x -= lowbit(x); }
    void right_up(int &x) { x += lowbit(x); }

public:
    BIT() { clear(); }
    void clear() { memset(this, 0, sizeof(*this)); }
    int size() { return sz; }

    // 點更新
    void update(int idx, int val = 1) {
        for (; idx <= Total; right_up(idx)) info[idx] += val;
        sz += val;
    }

    // 區間查詢 [1, idx]
    int lteq(int idx) {
        int sum = 0;
        for (; idx > 0; left_up(idx)) sum += info[idx];
        return sum;
    }
    int gt(int idx) { return sz - lteq(idx); }

    // 單點查詢（差分模式下）
    int count(int idx) {
        int sum = info[idx];
        for (int j = 1; j < lowbit(idx); j <<= 1) sum -= info[idx - j];
        return sum;
    }

    // 第 n 小（自上而下二分）
    int erase_nth(int n, bool erase = true) {
        int idx = Min2k;
        for (int k = idx / 2; k > 0; k >>= 1) {
            if (n <= info[idx]) { if (erase) info[idx]--; idx -= k; }
            else { n -= info[idx]; idx += k; if (idx > Total) idx -= k; }
        }
        if (erase) sz--;
        return idx;
    }
    int operator[](int n) { return erase_nth(n, false); }
};