HDU 1559 最大子矩陣——二維樹狀數組模板題詳解

HDU 1559 是一道經典的二維樹狀數組（2D Binary Indexed Tree）應用題。給定一個 m × n 的整數矩陣，要求找出大小為 x × y 的子矩陣，使其元素和最大。資料範圍 m, n < 1000，暴力枚舉 O(m²n²) 會超時，必須用二維樹狀數組將區間和查詢優化到 O(log m · log n)。

一、核心公式：二維前綴和與樹狀數組

定義 sum(x, y) 為從 (1,1) 到 (x,y) 的矩形區域和。任意子矩陣 (x1,y1) ~ (x2,y2) 的和可由容斥原理求得：

query(x1, y1, x2, y2) = sum(x2, y2) - sum(x1-1, y2) - sum(x2, y1-1) + sum(x1-1, y1-1)

二、樹狀數組核心操作

// 低位函數
inline int lowbit(int x) { return x & (-x); }

// 單點加值：在 (x,y) 加上 val
void add(int x, int y, int val) {
    for (int i = x; i <= n; i += lowbit(i))
        for (int j = y; j <= m; j += lowbit(j))
            bit[i][j] += val;
}

// 前綴和查詢：(1,1) 到 (x,y)
int sum(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 += bit[i][j];
    return res;
}

三、完整 AC 代碼（含註釋）

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int MAXN = 1010;
int n, m;
int bit[MAXN][MAXN];

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

void add(int x, int y, int val) {
    for (int i = x; i <= n; i += lowbit(i))
        for (int j = y; j <= m; j += lowbit(j))
            bit[i][j] += val;
}

int sum(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 += bit[i][j];
    return res;
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int x, y;
        scanf("%d%d%d%d", &n, &m, &x, &y);
        memset(bit, 0, sizeof(bit));

        // 讀入矩陣並建樹
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j) {
                int val; scanf("%d", &val);
                add(i, j, val);
            }

        int ans = INT_MIN;
        // 枚舉所有 x×y 子矩陣的左上角
        for (int i = 1; i + x - 1 <= n; ++i)
            for (int j = 1; j + y - 1 <= m; ++j) {
                int x2 = i + x - 1, y2 = j + y - 1;
                int cur = sum(x2, y2) - sum(i-1, y2) - sum(x2, j-1) + sum(i-1, j-1);
                ans = max(ans, cur);
            }
        printf("%d\n", ans);
    }
    return 0;
}

四、複雜度分析

• 建樹：O(n·m·log n·log m)
• 枚舉子矩陣：O((n-x+1)·(m-y+1)·log n·log m)
• 空間：O(n·m)

在 n,m ≤ 1000 且 3 秒時限下完全足夠。

五、常見坑點提醒

1. 下標從 1 開始，輸入座標直接對應，無需離散化。
2. memset(bit, 0, sizeof(bit)) 每組測資必須清零。
3. 答案可能為負數，初始值用 INT_MIN 而非 0。