如何高效實現二維樹狀數組

一、樹狀數組的介紹

樹狀數組，又叫二叉索引樹，是一種數據結構，用於高效地進行單點更新和區間查詢。樹狀數組主要用於處理靜態或動態數組的前綴和，即快速求出一個數組前綴中所有元素的和。

樹狀數組可以將普通數組中的前綴和轉化為數據結構中的前綴和，這樣就可以快速查詢區間和，並且支持快速單點修改操作。樹狀數組的優點在於其空間複雜度低，實現簡單，而且複雜度都是 O(log n) 級別，因此廣泛應用於各類問題的求解。

二、二維樹狀數組的原理

對於二維的情況，可以將樹狀數組中的一維數組再當成樹狀數組處理，建立起二維樹狀數組，用於處理二維數組的前綴和，即可以快速查詢二維數組中矩形區間的和等問題。二維樹狀數組的建立和查詢都與一維樹狀數組類似，只是需要對於兩個維度分別進行處理。具體實現時，可以將二維數組中的行和列都進行處理，分別建立兩個一維樹狀數組。這樣，在進行矩形區間查詢時，則可以將其轉化為四個一維區間查詢問題。

三、如何高效實現二維樹狀數組

1. 初始化和更新操作

int lowbit(int x) {
    return x & -x; // 求 x 的二進位中最低位的 1 所對應的值
}

void update2D(int x, int y, int k) {
    for (int i = x; i <= n; i += lowbit(i)) {
        for (int j = y; j <= m; j += lowbit(j)) {
            c[i][j] += k;
        }
    }
}

對於二維樹狀數組的初始化和更新操作，同樣需要使用 lowbit 函數來區分每一個區間。在此，我們定義 lowbit 函數為求一個二進位數中末尾 1 的位置，得到的結果即為取余時當前區間的長度。

2. 查詢操作

int query2D(int x, int y) {
    int res = 0;
    for (int i = x; i > 0; i -= lowbit(i)) {
        for (int j = y; j > 0; j -= lowbit(j)) {
            res += c[i][j];
        }
    }
    return res;
}

int query2DRange(int x1, int y1, int x2, int y2) {
    return query2D(x2, y2) - query2D(x2, y1 - 1) - query2D(x1 - 1, y2) + query2D(x1 - 1, y1 - 1);
}

對於二維樹狀數組的查詢操作，需要進行一個四個區間的操作。在此，我們需要兩個一維樹狀數組 c1 和 c2 分別維護行和列方向的前綴和，然後可以通過對四個點的坐標進行四個區間的加減計算得到對應的矩陣區間和。

四、總結

二維樹狀數組是一種十分實用的數據結構，可以方便地處理二維數組的前綴和和矩形區間查詢等問題。在實現時，需要注意橫縱坐標的區分，以及維護兩個一維樹狀數組分別用於維護行和列的前綴和，然後再進行四個區間的加減匯總操作。在實際應用中，二維樹狀數組能夠較為高效地解決一些問題，因此在需要處理二維數組的前綴和等問題時，可以考慮使用二維樹狀數組。