樹狀數組（Fenwick Tree）核心原理與 POJ 3928 實戰應用

樹狀數組簡介

樹狀數組是一種**巧妙的資料結構**，專門解決**動態區間和查詢**與**單點更新**問題，時間複雜度均為 O(log n)，空間 O(n)，代碼極短、常數極小。

核心概念：lowbit

lowbit(x) = x & (-x)，返回 x 二進制表示中**最低位 1 所代表的值**。
例：lowbit(6) = lowbit(110₂) = 2，lowbit(8) = 8。

陣列定義

• a[i]：原始陣列（1-based）。
• c[i]：樹狀數組，**儲存區間和** a[i] + a[i-1] + ... + a[i-lowbit(i)+1]。

兩大核心操作

1. 查詢前綴和 sum(i)

int sum(int i) {
    int res = 0;
    while (i > 0) {
        res += c[i];
        i -= lowbit(i);  // 向左跳躍
    }
    return res;
}

原理：將 [1, i] 分解為若干個 c[] 覆蓋的不相交區間。

2. 單點更新 add(i, delta)

void add(int i, int delta) {
    while (i <= n) {
        c[i] += delta;
        i += lowbit(i);  // 向右跳躍，更新所有覆蓋 i 的區間
    }
}

POJ 3928 題目分析

題意：n 位隊員能力值互不相同，裁判住在某位置，求所有隊員對裁判的「不滿度」總和（定義略）。關鍵轉化：對每個裁判位置，需要知道**左側比他小**與**右側比他大**的隊員數，或相反。用樹狀數組維護「已處理隊員的位置分布」。

解題關鍵步驟

1. 將隊員按能力值**從小到大排序**，得到排名陣列 c[]（c[i] 為第 i 小能力值的原始位置）。
2. 遍歷排名，對於第 i 小的隊員（位置 pos = c[i]）：
   • 查詢 sum(pos) = 左側已處理（能力較小）隊員數。
   • 左側較大 = i-1 - sum(pos)。
   • 右側較小 = pos - 1 - sum(pos)。
   • 右側較大 = n - pos - (i-1 - sum(pos))。
   • 根據題目公式累加貢獻。
3. 更新樹狀數組：add(pos, 1) 標記該位置已有隊員。

核心代碼片段

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

int sum(int i) {
    int s = 0;
    while (i > 0) { s += bit[i]; i -= lowbit(i); }
    return s;
}
void add(int i, int v) {
    while (i <= n) { bit[i] += v; i += lowbit(i); }
}

int main() {
    // ... 讀入、排序獲取 c[] ...
    add(c[1], 1);  // 最小能力值先入樹
    long long ans = 0;
    for (int i = 2; i < n; i++) {
        int pos = c[i];
        int leftSmall = sum(pos);
        int leftBig = (i-1) - leftSmall;
        int rightSmall = pos - 1 - leftSmall;
        int rightBig = n - pos - leftBig;
        ans += (long long)leftSmall * rightBig + (long long)leftBig * rightSmall;
        add(pos, 1);
    }
    printf("%lld\n", ans);
}

總結

樹狀數組以「lowbit 分解區間」的精妙設計，完美平衡了查詢與更新效率。POJ 3928 展示了其在**離線排序 + 動態順序統計**中的經典應用模式：排序轉化順序關係，樹狀數組維護位置分布，O(n log n) 輕鬆解決 n=20000 規模問題。