技術文章 » 理解樹狀陣列這一篇文章就夠啦

理解樹狀陣列這一篇文章就夠啦

2023-02-22 06:02:04

樹狀陣列

TODO：

前言

在閱讀本文之前，您可能需要先了解位運算、二元樹以及字首和與差分等相關知識

本文中，若無特殊說明，數列下標均從 \(1\) 開始

引入

什麼是樹狀陣列

樹狀陣列是一種 通過陣列來模擬"樹形"結構，支援單點修改和區間查詢的資料結構

因為它是通過二進位制的性質構成的，所以它又被叫做 二進位制索引樹（\(Binary\ Indexed\ Tree\)），也被稱作 \(FenWick\ Tree\)

用於解決什麼問題

樹狀陣列常用於動態維護區間資訊

例題

P3374 【模板】樹狀陣列 1 - 洛谷

題目簡述：對數列進行單點修改以及區間求和

常規解法

單點修改的時間複雜度為 \(O(1)\)

區間求和的時間複雜度為 \(O(n)\)

共 \(m\) 次操作，則總時間複雜度為 \(O(n\times m)\)

import java.io.*;

public class Main {
    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int get() throws IOException {
        in.nextToken();
        return (int) in.nval;
    }

    public static void main(String[] args) throws IOException {
        PrintWriter out = new PrintWriter(System.out);
        int n = get(), m = get();
        int[] a = new int[n];
        for (int i = 0; i < n; ++i) a[i] = get();
        while (m-- != 0) {
            int command = get(), x = get(), y = get();
            if (command == 1) {
                a[x - 1] += y;
            } else {
                int sum = 0;
                for (int i = x - 1; i < y; i++) sum += a[i];
                out.println(sum);
            }
        }
        out.close();
    }
}

字首和解法

區間求和通過字首和優化，但單點修改的時候需要修改字首和陣列

單點修改的時間複雜度為 \(O(n)\)

區間求和的時間複雜度為 \(O(1)\)

共 \(m\) 次操作，則總時間複雜度為 \(O(n\times m)\)

import java.io.*;

public class Main {
    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int get() throws IOException {
        in.nextToken();
        return (int) in.nval;
    }

    public static void main(String[] args) throws IOException {
        PrintWriter out = new PrintWriter(System.out);
        int n = get(), m = get();
        int[] sum = new int[n + 1];
        for (int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + get();
        while (m-- != 0) {
            int command = get(), x = get(), y = get();
            if (command == 1) {
                for (int i = x; i <= n; ++i) sum[i] += y;
            } else {
                System.out.println(sum[y] - sum[x - 1]);
            }
        }
        out.close();
    }
}

樹狀陣列解法

可以發現上述兩種方法，不是單點修改的時間複雜度過高，就是區間求和的時間複雜度過高，導致最壞時間複雜度很高。

於是，樹狀陣列出現了，它用來平衡這兩種操作的時間複雜度。

樹狀陣列的思想

每個正整數都可以表示為若干個 \(2\) 的冪次之和（二進位制基本原理）

類似的，每次求字首和，我們也希望將區間 \([1,i]\) 分解成 \(\log_2 i\) 個子集的和

也就是如果 \(i\) 的二進位制表示中如果有 \(k\) 個 \(1\)，我們就希望將其分解為 \(k\) 個子集之和

樹狀陣列的樹形態與二元樹

每一個矩形代表樹的一個節點，矩形大小表示所管轄的數列區間範圍

一顆二元樹的形態如下圖所示

我們發現，對於具有逆運算的運算，如求和運算，有如下式子

\[sum(l,r)= sum(l,k)+sum(k+1,r)\\ sum(k+1,r)=sum(l,r)-sum(l,k) \]

實際上，許多資料可以通過一些節點的差集獲得

因此，上述二元樹的一些節點可以進行刪除

樹狀陣列的形態如下圖所示

管轄區間

對於下圖中的樹狀陣列（黑色數位代表原始陣列 \(A_i\) 紅色數位代表樹狀陣列中的每個節點資料 \(C_i\)）

從圖中可以看出：

樹狀陣列 管轄區間
\(C_1\) \(A[1\dots1]\)
\(C_2\) \(A[1\dots2]\)
\(C_3\) \(A[3\dots3]\)
\(C_4\) \(A[1\dots4]\)
\(C_5\) \(A[5\dots5]\)
\(C_6\) \(A[5\dots6]\)
\(C_7\) \(A[7\dots7]\)
\(C_8\) \(A[1\dots8]\)

那麼如何通過計算機確定 \(C_x\) 的管轄區間呢？

前面提到過樹狀陣列的思想是基於二進位制的

樹狀陣列中，規定 \(C_x\) 所管轄的區間長度為 \(2^k\)，其中：

  • 設二進位制最低位為第 \(0\) 位，則 \(k\) 恰好為 \(x\) 的二進位制表示中，最低位的 \(1\) 所在的二進位制位數；
  • \(2^k\)（\(C_x\) 的管轄區間長度）恰好為 \(x\) 二進位制表示中，最低位的 \(1\) 以及後面所有 \(0\) 組成的數。

以 \(C_{88}\) 所管轄的區間為例

因為 \((88)_{10}=(1011000)_2\)，其二進位制最低位的 \(1\) 及後面的 \(0\) 組成的二進位制是 \((1000)_2=(8)_{10}\)，所以，\(C_{88}\) 管理 \(8\) 個 \(A\) 陣列中的元素。

因此，\(C_{88}\) 代表 \(A[81\dots88]\) 的區間資訊。

我們記 \(x\) 二進位制最低位 \(1\) 以及後面的 \(0\) 組成的數為 \(lowbit(x)\)，則 \(C_x\) 管轄的區間就是 \(A[x-lowbit(x)+1,x]\)

其中 lowbit(x) = x & (~x + 1) = x & -x

樹狀陣列樹的性質

性質比較多，下面列出重要的幾個性質，更多性質請參見OI Wiki，下面表述忽略二進位制前導零

  1. 節點 \(u\) 的父節點為 \(u+lowbit(u)\)

  2. 設節點 \(u=s\times 2^{k+1}+2^k\)，則其兒子數量為 \(k=log_2lowbit(u)\)（即 \(u\) 的二進位制表示中尾隨 \(0\) 的個數），這 \(k\) 個兒子的編號分別為 \(u-2^t(0\le t<k)\)

    如 \(k=3\)，\(u\) 的二進位制表示為 1000，則 \(u\) 有三個兒子，這三個兒子的二進位制編號分別為 111、110、100

  3. 節點 \(u\) 的所有兒子對應 \(C_u\) 的管轄區間恰好拼接成 \([lowbit(u),u-1]\)

    • 如 \(k=3\)，\(u\) 的二進位制表示為 1000，\(u\) 的三個兒子的二進位制編號分別為 111、110、100

      C[100]表示A[001~100]，C[110]表示A[101~110]，C[111]表示A[111~111]

      上述三個兒子管轄區間的並集恰好是 A[001~111]，即 \([lowbit(u),u-1]\)

單點修改

根據管轄區間，逐層維護管轄區間包含這個節點的父節點（節點 \(u\) 的父節點為 \(u+lowbit(u)\)）

void add(int x, int val) { // A[x] 加上 val
    for (; x <= n; x += x & -x) {
        C[x] += val;
    }
}

區間查詢

區間查詢問題可以轉化為字首查詢問題（字首和思想），也就是查詢區間 \([l,r]\) 的和，可以轉化為 \(A[1\dots r]\)與\(A[1\dots l-1]\)的差集

如計算 \(A[4\dots7]\) 的值，可以轉化為求 \(A[1\dots7]\) 和 \(A[1\dots3]\) 再相減

字首查詢的過程是：根據管轄區間，不斷拆分割區間，查詢上一個字首區間

對於 \(A[1\dots x]\) 的字首查詢過程如下：

  • 從 \(x\) 開始向前拆分，有 \(C_x\) 管轄 \(A[x-lowbit(x)+1\dots x]\)
  • 令 \(x\gets x-lowbit(x)\)
  • 重複上述過程，直至 \(x=0\)

由於 \(x-lowbit(x)\) 的算術意義是去除二進位制最後一個 \(1\)，因此也可以寫為 \(x\&(x-1)\)

// 查詢字首 A[1...x] 的和
int getSum(int x) {
    int ans = 0;
    for (; x != 0; x &= x - 1) ans += C[x];
    //for (; x != 0; x -= x & -x) ans += C[x];
    return ans;
}
// 查詢區間 A[l...r] 的和
int queryRange(int l, int r) {
    return getSum(r) - getSum(l - 1);
}

上述過程進行了兩次字首查詢，實際上，對於 \(l-1\) 和 \(r\) 的字首區間是相同的，我們不需要計算

// 查詢區間 A[l...r] 的和
int queryRange(int l, int r) {
    // return getSum(r) - getSum(l - 1);
    int ans = 0;
    --l;
    while (l < r) {
        // 左邊層數低，左邊向前跳
        int lowbitl = l & -l, lowbitr = r & -r;
        if (l != 0 && lowbitl < lowbitr) {
            ans -= C[l];
            l -= lowbitl;
        } else {
            ans += C[r];
            r -= lowbitr;
        }
    }
    return ans;
}

單點查詢

單點查詢可以轉化為區間查詢，需要兩次字首查詢，但有更好的方法

\(x\) 所管轄的區間為 \(C_x=A[x-lowbit(x)+1\dots x]\)，而節點 \(x\) 的所有子節點的並集恰好為 \(A[x-lowbit(x)+1\dots x-1]\)

則 \(A[x]=C_x-A[x-lowbit(x)+1\dots x-1]\)

對於 \(A[x]\) 的更好的查詢過程如下：

  • 查詢 \(x\) 所管轄的區間 \(C_x\)
  • 減去 \(x\) 的所有子節點的資料
//int queryOne(int x) {
//    return queryRange(x, x);
//}
int queryOne(int x) {
    int ans = c[x];
    int lca = x & x - 1; // x - lowbit(x)
    for (int i = x - 1; i > lca; i &= i - 1) {
        ans -= C[i];
    }
    return ans;
}

建樹

可以通過呼叫單調修改方法進行建樹，時間複雜度 \(O(n\log n)\)

時間複雜度為 \(O(n)\) 的建樹方法有如下兩種：

方法一：

每一個節點的值是由所有與自己直接相連的兒子的值求和得到的。因此可以倒著考慮貢獻，即每次確定完兒子的值後，用自己的值更新自己的直接父親。

void init() {
    for (int i = 1; i <= n; ++i) {
        C[i] += A[i];
        // 找 i 的父節點
        int father = i + (i & -i);
        if (father <= n) C[father] += C[i];
    }
}

方法二：

由於 \(C_x\) 所管轄的區間是 \([x-lowbit(x)+1,x]\)，則可以預處理 \(sum\) 字首和陣列，再通過 \(sum[x]-sum[x-lowbit(x)]\) 計算 \(C_x\)

我們也可以先用 \(C\) 陣列計算字首和，再倒著計算 \(C_x\)（因為正著計算會導致前面的值被修改，與 \(01\) 揹包優化相同）

同樣的 \(x-lowbit(x)\) 可以寫為 \(x\&(x-1)\)

void init() {
    for (int i = 1; i <= n; ++i) {
        C[i] = C[i - 1] + A[i];
    }
    for (int i = n; i > 0; --i) {
        C[i] -= C[i & i - 1];
    }
}

複雜度分析

空間複雜度為 \(O(n)\)

單點修改、單點查詢、區間查詢操作的時間複雜度均為 \(O(\log{n})\)

建樹的時間複雜度為 \(O(n\log n)\) 或 \(O(n)\)

Code

import java.io.*;

public class Main {
    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int get() throws IOException {
        in.nextToken();
        return (int) in.nval;
    }

    static int n;
    static int[] c, a;

    static void add(int x, int val) {
        for (; x <= n; x += x & -x) {
            c[x] += val;
        }
    }

    static int getSum(int x) {
        int ans = 0;
        for (; x != 0; x &= x - 1) ans += c[x];
        return ans;
    }

    static int queryOne(int x) {
        int ans = c[x];
        int lca = x & x - 1;
        for (int i = x - 1; i > lca; i &= i - 1) {
            ans -= c[i];
        }
        return ans;
    }

    static int queryRange(int l, int r) {
        int ans = 0;
        --l;
        while (l < r) {
            // 左邊層數低，左邊向前跳
            int lowbitl = l & -l, lowbitr = r & -r;
            if (l != 0 && lowbitl < lowbitr) {
                ans -= c[l];
                l -= lowbitl;
            } else {
                ans += c[r];
                r -= lowbitr;
            }
        }
        return ans;
    }

    static void init() {
        for (int i = 1; i <= n; ++i) {
            c[i] += a[i];
            int father = i + (i & -i);
            if (father <= n) c[father] += c[i];
        }
    }

    public static void main(String[] args) throws IOException {
        PrintWriter out = new PrintWriter(System.out);
        n = get();
        int m = get();
        a = new int[n + 1];
        c = new int[n + 1];
        for (int i = 1; i <= n; ++i) a[i] = get();
        init();
        while (m-- != 0) {
            int command = get(), x = get(), y = get();
            if (command == 1) {
                add(x, y);
            } else {
                out.println(queryRange(x, y));
            }
        }
        out.close();
    }
}

要點總結

  • 注意樹狀陣列的樹型特徵

  • \(x\) 的管轄元素個數為\(lowbit(x)\)，管轄區間為 \([x-lowbit(x)+1,x]\)

  • 樹狀陣列中，\(x\) 的父節點編號為 \(x+lowbit(x)\)

  • 樹狀陣列的二叉查詢樹中，\(x\) 的父節點（也即字首區間）編號為 \(x-lowbit(x)\)

  • 樹狀陣列是一個維護字首資訊的樹型資料結構

  • 樹狀陣列維護的資訊需要滿足結合律以及可差分（因為一些資料需要通過其他資料的差集獲得）兩個性質，如加法，乘法，互斥或等

    結合律：\((x\circ y)\circ z=x\circ(y\circ z)\)，其中 \(\circ\) 是一個二元運運算元。

    可差分：具有逆運算的運算，即已知 \(x\circ y\) 和 \(x\) 可以求出 \(y\)

  • 有時樹狀陣列在其他輔助陣列（如差分陣列）的幫助下，可以解決更多的問題

  • 由於樹狀陣列需要逆運算抵消掉原運算（如加和減），而線段樹只需要逐層拆分割區間，在合併區間資訊，並不需要抵消部分數值，所以說樹狀陣列能解決的問題是線段樹能解決的問題的子集

  • 樹狀陣列下標也可以從 \(0\) 開始，此時 \(x\) 的父節點編號為 \(x|(x+1)\)，\(x\) 的管轄元素個數為 \(x-(x\&(x+1))+1\)，管轄區間為 \([x\&(x+1),x]\)

樹狀陣列封裝類

一個 \(Java\) 的樹狀陣列封裝類

class BIT {
    int n;
    int[] c;

    // 請保證 a 的資料從下標 1 開始
    public void init(int[] a) {
        // assert(a.length > n);
        for (int i = 1; i <= n; ++i) {
            c[i] += a[i];
            int father = i + (i & -i);
            if (father <= n) c[father] += c[i];
        }
    }

    public BIT(int _n) {
        n = _n;
        c = new int[n + 1];
    }

    // 請保證 a 的資料從下標 1 開始
    public BIT(int[] a, int _n) {
        n = _n;
        c = new int[n + 1];
        init(a);
    }

    public void add(int i, int val) {
        if (i > n) return;
        for (; i <= n; i += i & -i) {
            c[i] += val;
        }
    }

    public int preSum(int i) {
        int ans = 0;
        for (; i != 0; i &= i - 1) ans += c[i];
        return ans;
    }

    public int single(int i) {
        int ans = c[i];
        int lca = i & i - 1;
        for (int j = i - 1; j > lca; j &= j - 1) {
            ans -= c[j];
        }
        return ans;
    }

    public int range(int l, int r) {
        int ans = 0;
        --l;
        while (l < r) {
            // 左邊層數低，左邊向前跳
            int lowbitl = l & -l, lowbitr = r & -r;
            if (l != 0 && lowbitl < lowbitr) {
                ans -= c[l];
                l -= lowbitl;
            } else {
                ans += c[r];
                r -= lowbitr;
            }
        }
        return ans;
    }
}

進階

區間修改+單點查詢

P3368 【模板】樹狀陣列 2 - 洛谷

一些操作對映到字首陣列或者差分陣列上可能會變得很簡單

考慮序列 \(a\) 的差分陣列 \(d\)，其中 \(d_i=a_i-a_{i-1}\)。

則對於序列 \(a\) 的區間 \([l,r]\) 加 \(value\) 可以轉化為 \(d_l+value\) 和 \(d_{r+1}-value\)，也就是差分陣列上的兩次單點操作。

因此 \(a_x=\sum_{i=1}^xd_i\) 選擇通過樹狀陣列維護差分陣列

import java.io.*;

public class Main {
    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int get() throws IOException {
        in.nextToken();
        return (int) in.nval;
    }

    static int n;
    static int[] d, a;

    static void add(int x, int val) {
        for (; x <= n; x += x & -x) {
            d[x] += val;
        }
    }

    static int getSum(int x) {
        int ans = 0;
        for (; x != 0; x &= x - 1) ans += d[x];
        return ans;
    }

    public static void main(String[] args) throws IOException {
        PrintWriter out = new PrintWriter(System.out);
        n = get();
        int m = get();
        a = new int[n + 1];
        d = new int[n + 1];
        for (int i = 1; i <= n; ++i) a[i] = get();
        // 初始化 c[i] 為 0，僅在 c 上差分，可以不用對 a 進行差分
        while (m-- != 0) {
            int command = get();
            if (command == 1) {
                int x = get(), y = get(), k = get();
                if (k == 0) continue;
                add(x, k);
                if (y + 1 <= n) add(y + 1, -k);
            } else {
                int x = get();
                out.println(getSum(x) + a[x]);
            }
        }
        out.close();
    }
}

區間修改+區間查詢

P3372 【模板】線段樹 1 - 洛谷

對於區間查詢 \(a[l\dots r]\)，同樣選擇轉化為字首查詢 \(a[1\dots r]\) 及 \(a[1\dots l-1]\) 的差集

考慮序列 \(a\) 的差分陣列 \(d\)，其中 \(d_i=a_i-a_{i-1}\)。由於差分陣列的字首和就是原陣列，則 \(a_i=\sum_{j=1}^id_j\)

所以，字首查詢變為 \(\sum_{i=1}^x a_i=\sum_{i=1}^x \sum_{j=1}^id_j\)

上式可表述為下圖藍色部分面積

橫著看看不出什麼，但豎著看會發現每個資料加的個數與 \(x\) 有關

\(d_x\) 會加 \(1\) 次，\(d_{x-1}\) 會加 \(2\) 次，\(\dots\) ，\(d_2\) 會加 \(x-1\) 次，\(d_1\) 會加 \(x\) 次

也就是 \(d_i\) 會加 \(x-i+1\)，加法轉化為乘法可得

\[\begin{aligned} \sum_{i=1}^x a_i&=\sum_{i=1}^x \sum_{j=1}^id_j\\ &=\sum_{i=1}^{x}d_i\times(x-i+1)\\ &=\sum_{i=1}^xd_i\times(x+1)-\sum_{i=1}^{x}d_i\times i\\ &=(x+1)\times\sum_{i=1}^xd_i-\sum_{i=1}^{x}d_i\times i \end{aligned} \]

又因為 \(\sum_{i=1}^xd_i\) 與 \(\sum_{i=1}^{x}d_i\times i\) 不能推導推匯出另一個

因此需要用兩個樹狀陣列分別維護 \(d_i\) 與 \(d_i\times i\)

  • 用於維護 \(d_i\) 的樹狀陣列，對於每次對 \([l,r]\) 加 \(k\) 轉化為 \(d[l]+k\) 與 \(d[r+1]-k\)

  • 用於維護 \(d_i\times i\) 的樹狀陣列，對於每次對 \([l,r]\) 加 \(k\) 轉化為

    \((d[l]+k)\times l=d[l]\times l+l\times k\) 與

    \((d[r+1]-k)\times (r+1)=d[r+1]\times (r+1)-(r+1)\times k\)

    即在原來的基礎上加上 \(l\times k\) 與減去 \((r+1)\times k\)

import java.io.*;

public class Main {

    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int get() throws IOException {
        in.nextToken();
        return (int) in.nval;
    }

    public static void main(String[] args) throws IOException {
        PrintWriter out = new PrintWriter(System.out);
        int n = get(), m = get();
        int[] a = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            a[i] = get();
        }
        // 求字首和
        for (int i = 1; i <= n; ++i) {
            a[i] += a[i - 1];
        }
        // 同樣的，初始化為 0，僅在空陣列上差分
        BIT tree1 = new BIT(n), tree2 = new BIT(n);
        while (m-- != 0) {
            int command = get(), x = get(), y = get();
            if (command == 1) {
                long k = get();
                tree1.add(x, k);
                tree1.add(y + 1, -k);
                tree2.add(x, x * k);
                tree2.add(y + 1, -(y + 1) * k);
            } else {
                // A[1...y] 的和
                long preY = a[y] + (y + 1) * tree1.preSum(y) - tree2.preSum(y);
                // A[1...x-1] 的和
                --x;
                long preX = a[x] + (x + 1) * tree1.preSum(x) - tree2.preSum(x);
                out.println(preY - preX);
            }
        }
        out.close();
    }
}

class BIT {
    int n;
    long[] c;

    // 請保證 a 的資料從下標 1 開始
    public void init(int[] a) {
        // assert(a.length > n);
        for (int i = 1; i <= n; ++i) {
            c[i] += a[i];
            int father = i + (i & -i);
            if (father <= n) c[father] += c[i];
        }
    }

    public BIT(int _n) {
        n = _n;
        c = new long[n + 1];
    }

    // 請保證 a 的資料從下標 1 開始
    public BIT(int[] a, int _n) {
        n = _n;
        c = new long[n + 1];
        init(a);
    }

    public void add(int i, long val) {
        if (i > n) return;
        for (; i <= n; i += i & -i) {
            c[i] += val;
        }
    }

    public long preSum(int i) {
        long ans = 0;
        for (; i != 0; i &= i - 1) ans += c[i];
        return ans;
    }

    public long single(int i) {
        long ans = c[i];
        int lca = i & i - 1;
        for (int j = i - 1; j > lca; j &= j - 1) {
            ans -= c[j];
        }
        return ans;
    }

    public long range(int l, int r) {
        long ans = 0;
        --l;
        while (l < r) {
            // 左邊層數低，左邊向前跳
            int lowbitl = l & -l, lowbitr = r & -r;
            if (l != 0 && lowbitl < lowbitr) {
                ans -= c[l];
                l -= lowbitl;
            } else {
                ans += c[r];
                r -= lowbitr;
            }
        }
        return ans;
    }
}

也可以寫成封裝類的形式

import java.io.*;

public class Main {

    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int get() throws IOException {
        in.nextToken();
        return (int) in.nval;
    }

    public static void main(String[] args) throws IOException {
        PrintWriter out = new PrintWriter(System.out);
        int n = get(), m = get();
        int[] a = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            a[i] = get();
        }
        // 求字首和
        for (int i = 1; i <= n; ++i) {
            a[i] += a[i - 1];
        }
        ExBIT tree = new ExBIT(n);
        while (m-- != 0) {
            int command = get(), x = get(), y = get();
            if (command == 1) {
                tree.add(x, y, get());
            } else {
                out.println(a[y] - a[x - 1] + tree.range(x, y));
            }
        }
        out.close();
    }
}

class BIT {
    int n;
    long[] c;

    // 請保證 a 的資料從下標 1 開始
    public void init(int[] a) {
        // assert(a.length > n);
        for (int i = 1; i <= n; ++i) {
            c[i] += a[i];
            int father = i + (i & -i);
            if (father <= n) c[father] += c[i];
        }
    }

    public BIT(int _n) {
        n = _n;
        c = new long[n + 1];
    }

    // 請保證 a 的資料從下標 1 開始
    public BIT(int[] a, int _n) {
        n = _n;
        c = new long[n + 1];
        init(a);
    }

    public void add(int i, long val) {
        if (i > n) return;
        for (; i <= n; i += i & -i) {
            c[i] += val;
        }
    }

    public long preSum(int i) {
        long ans = 0;
        for (; i != 0; i &= i - 1) ans += c[i];
        return ans;
    }

    public long single(int i) {
        long ans = c[i];
        int lca = i & i - 1;
        for (int j = i - 1; j > lca; j &= j - 1) {
            ans -= c[j];
        }
        return ans;
    }

    public long range(int l, int r) {
        long ans = 0;
        --l;
        while (l < r) {
            // 左邊層數低，左邊向前跳
            int lowbitl = l & -l, lowbitr = r & -r;
            if (l != 0 && lowbitl < lowbitr) {
                ans -= c[l];
                l -= lowbitl;
            } else {
                ans += c[r];
                r -= lowbitr;
            }
        }
        return ans;
    }
}

// 差分增量
class ExBIT {
    int n;
    BIT tree1, tree2;

    public ExBIT(int _n) {
        n = _n;
        tree1 = new BIT(_n);
        tree2 = new BIT(_n);
    }

    // 區間加對應差分陣列的 兩個端點操作
    public void add(int l, int r, long k) {
        tree1.add(l, k);
        tree1.add(r + 1, -k);
        tree2.add(l, l * k);
        tree2.add(r + 1, -(r + 1) * k);
    }

    // 差分增量的字首和
    public long preSum(int i) {
        return (i + 1) * tree1.preSum(i) - tree2.preSum(i);
    }

    // 差分增量的區間和
    public long range(int l, int r) {
        return preSum(r) - preSum(l - 1);
    }
}

題目

P4939 Agent2 - 洛谷

題目連結

題意簡述：有兩個操作

  1. 對區間 \([l,r]\) 的數均加 \(1\)
  2. 查詢第 \(x\) 個數的值

進階中的 區間修改+單點查詢

import java.io.*;

public class Main {
    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int get() throws IOException {
        in.nextToken();
        return (int) in.nval;
    }

    static int n;
    static int[] d;

    static void add(int x, int val) {
        for (; x <= n; x += x & -x) {
            d[x] += val;
        }
    }

    static int getSum(int x) {
        int ans = 0;
        for (; x != 0; x &= x - 1) ans += d[x];
        return ans;
    }

    public static void main(String[] args) throws IOException {
        PrintWriter out = new PrintWriter(System.out);
        n = get();
        int m = get();
        d = new int[n + 1];
        while (m-- != 0) {
            int command = get();
            if (command == 0) {
                int x = get(), y = get();
                add(x, 1);
                if (y + 1 <= n) add(y + 1, -1);
            } else {
                int x = get();
                out.println(getSum(x));
            }
        }
        out.close();
    }
}

P5057 簡單題 - 洛谷

題目連結

題目簡述：有兩個操作

  1. 對區間 \([l,r]\) 的數進行反轉（1變0，0變1）
  2. 單點查詢

反轉等同於與 \(1\) 互斥或，於是題目變成了維護區間互斥或和單點查詢，同樣選擇差分序列，只不過是互斥或的差分。

而互斥或也滿足樹狀陣列的兩個要求，因此使用樹狀陣列解決該題

import java.io.*;

public class Main {

    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int get() throws IOException {
        in.nextToken();
        return (int) in.nval;
    }

    static int n, m;
    static int[] c;

    static void change(int x) {
        for (; x <= n; x += x & -x) c[x] ^= 1;
    }

    static int askPre(int x) {
        int ans = 0;
        for (; x != 0; x &= x - 1) ans ^= c[x];
        return ans;
    }

    public static void main(String[] args) throws IOException {
        PrintWriter out = new PrintWriter(System.out);
        n = get();
        m = get();
        c = new int[n + 1];
        while (m-- != 0) {
            int command = get();
            if (command == 1) {
                int l = get(), r = get();
                change(l);
                if (r < n) change(r + 1);
            } else {
                out.println(askPre(get()));
            }
        }
        out.close();
    }
}

P1908 逆序對 - 洛谷

題目連結

題意簡述：求陣列中的逆序對

求解逆序對可以用歸併排序求解，此處不做討論

從前向後遍歷陣列，同時將其加入到桶中，記錄每個數出現的個數，並加上該位置之前且比當前數大的數的個數（有點繞，看例子可能會清晰點）

桶：用 \(cnt[i]\) 表示目前 \(i\) 出現的個數，初始化均為 \(0\)

\(ans\)：表示目前逆序對的個數，初始化為 \(0\)

陣列: 1 3 5 4 2 1                            桶的下標: 0 1 2 3 4 5 6
一: 加入 1 到桶中 ans+=cnt[2...max]     ans=0      桶: 0 1 0 0 0 0 0
二: 加入 3 到桶中 ans+=cnt[4...max]     ans=0      桶: 0 1 0 1 0 0 0
三: 加入 5 到桶中 ans+=cnt[6...max]     ans=0      桶: 0 1 0 1 0 1 0
四: 加入 4 到桶中 ans+=cnt[5...max]     ans=1      桶: 0 1 0 1 1 1 0
五: 加入 2 到桶中 ans+=cnt[3...max]     ans=4      桶: 0 1 1 1 1 1 0
六: 加入 1 到桶中 ans+=cnt[2...max]     ans=8      桶: 0 2 1 1 1 1 0

也就是需要求 \(i\) 時刻，桶中 \([a_i+1,max]\) 的和，其中 \(max\) 為所有資料中的最大值

也即實現 單點加 與 區間查詢，使用樹狀陣列求解

但是題目中 \(max\le 10^9\)，樹狀陣列的長度開不了那麼大

可以發現，該題中我們只關心資料間的相對大小關係，而不關心資料本身大小，採用離散化的方式，將資料縮小（一種對映關係）

舉個例子：

原資料: 1 100 200 500 50
新資料: 1 3 4 5 2
這樣最大的資料就縮小到了 5

程式碼如下：

import java.io.*;
import java.util.Arrays;

public class Main {
    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int get() throws IOException {
        in.nextToken();
        return (int) in.nval;
    }

    static int n;
    static int[] d;

    static void add(int x, int val) {
        for (; x <= n; x += x & -x) {
            d[x] += val;
        }
    }

    static int getSum(int x) {
        int ans = 0;
        for (; x != 0; x &= x - 1) ans += d[x];
        return ans;
    }

    // 離散化
    static void lis(int[] a, int n) {
        int[] temp = new int[n];
        System.arraycopy(a, 0, temp, 0, n);
        Arrays.sort(temp);
        for (int i = 0; i < n; ++i) {
            a[i] = Arrays.binarySearch(temp, a[i]) + 1;
        }
    }

    public static void main(String[] args) throws IOException {
        PrintWriter out = new PrintWriter(System.out);
        n = get();
        int[] num = new int[n];
        for (int i = 0; i < n; ++i) num[i] = get();
        lis(num, n);
        d = new int[n + 1];
        long ans = 0;
        for (int i = 0; i < n; ++i) {
            add(num[i], 1);
            ans += i - getSum(num[i]) + 1;
        }
        out.println(ans);
        out.close();
    }
}

參考資料

樹狀陣列 - OI Wiki