POJ 2029 Get Many Persimmon Trees：二維樹狀數組求矩形區域最大樹木數

問題轉化

W×H 網格中有 N 棵柿子樹（坐標 1-indexed）。給定矩形大小 S×T，可平移但不可旋轉，求能包含最多樹木的位置。
等價於：在二維前綴和矩陣中，找固定大小滑動窗口的最大和。

二維 BIT (Fenwick Tree) 實現

雖然靜態查詢用二維前綴和 O(1) 更快，但 BIT 適合動態增刪場景，此處作為模板練習。
核心操作：
add(x, y, v)：點更新。
sum(x, y)：矩形 [1,1]~[x,y] 前綴和。
區間和：sum(x2,y2) - sum(x1-1,y2) - sum(x2,y1-1) + sum(x1-1,y1-1)。

關鍵代碼

const int MAX = 105;
int bit[MAX][MAX];
void add(int x, int y, int v) {
    for (int i = x; i < MAX; i += i&-i)
        for (int j = y; j < MAX; j += j&-j)
            bit[i][j] += v;
}
int sum(int x, int y) {
    int s = 0;
    for (int i = x; i > 0; i -= i&-i)
        for (int j = y; j > 0; j -= j&-j)
            s += bit[i][j];
    return s;
}
int query(int x1, int y1, int x2, int y2) {
    return sum(x2,y2) - sum(x1-1,y2) - sum(x2,y1-1) + sum(x1-1,y1-1);
}

滑動窗口枚舉

int ans = 0;
for (int x = 1; x + S - 1 <= W; ++x)
    for (int y = 1; y + T - 1 <= H; ++y)
        ans = max(ans, query(x, y, x+S-1, y+T-1));

靜態優化：二維前綴和

預計算 pre[i][j]，查詢 O(1)，總 O(WH + N)。W,H ≤ 100 時極快，推薦實戰使用。

複雜度對比