hdu 1559 最大子矩阵 二维树状数组

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int arr[1010][1010], m, n, x, y;
int lowbit(int x)
{
    return x & -x;
}
///二维树状数组
void add(int x, int y, int tt)        ///单点修改
{
    for (int i = x; i < m; i += lowbit(i))
        for (int j = y; j < n; j += lowbit(j))
        {
            arr[i][j] += tt;
        }
}
int sum(int x, int y)
{
    int res = 0;
    for (int i = x; i; i -= lowbit(i))
        for (int j = y; j; j -= lowbit(j))
        {
            res += arr[i][j];
        }
    return res;
}
int query(int L, int B, int R, int T) ///矩阵求和
{
    return sum(R, T) + sum(L - 1, B - 1) - sum(R, B - 1) - sum(L - 1, T);
}
int main()
{
    int t;
    scanf("%d", &t);
    while (t--){
        scanf("%d%d%d%d", &m, &n, &x, &y);
        for (int i = 1; i <= m; i++){
            for (int j = 1; j <= n; j++){
                arr[i][j] = 0;
            }
        }
        int k, ans = 0, gg;
        for (int i = 1; i <= m; i++){
            for (int j = 1; j <= n; j++){
                scanf("%d", &k);
                add(i, j, k);
            }
        }
        for (int i = 1; i + x - 1 <= m; i++){
            for (int j = 1; j + y - 1 <= n; j++){
                gg = query(i, j, i + x - 1, j + y - 1);
                ans = max(ans, gg);
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}