Output 對於每組數據，輸出一個整數，表示子矩陣的最大和。
Sample Input
1 4 5 2 2 3 361 649 676 588 992 762 156 993 169 662 34 638 89 543 525 165 254 809 280
Sample Output
2474
Author lwg
Source HDU 2006-12 Programming Contest
二維樹狀數組模板題~~ 附上模板
void add(int x, int y, int d) {
int i, j;
for(i = x; i < N; i += lowbit(i))
for(j = y; j < N; j += lowbit(j))
mat[i][j] += d;
}
LL sum(int x, int y) {
LL res = 0;
int i, j;
for(i = x; i > 0; i -= lowbit(i))
for(j = y; j > 0; j -= lowbit(j))
res += mat[i][j];
return res;
}
該題主要注意一下sum的功能則是求從元素(1, 1)開始到(x, y)的總和，同樣，可以求出任意一個子矩陣內的所有元素之和，即sum(x2, y2) - sum(x1-1, y2) - sum(x2, y1-1) + sum(x1-1, y1-1)。
詳見代碼。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n,m;
int c[1010][1010];
int lowbit(int k)
{
return k&(-k);
}
void add(int x,int y,int num)
{
for (int i=x; i<=n; i+=lowbit(i))
{
for (int j=y; j<=m; j+=lowbit(j))
{
c[i][j]+=num;
}
}
}
int sum(int x,int y)
{
int s=0;
for (int i=x; i>0; i-=lowbit(i))
{
for (int j=y; j>0; j-=lowbit(j))
{
s+=c[i][j];
}
}
return s;
}
int main()
{
int t;
int ans,kk;
scanf("%d",&t);
while (t--)
{
int Max=0;
int x,y;
scanf("%d%d%d%d",&n,&m,&x,&y);
memset(c,0,sizeof(c));
for (int i=1; i<=n; i++)
{
for (int j=1; j<=m; j++)
{
scanf("%d",&kk);
add(i,j,kk);
}
}
int k=1;
for (int i=1; i+x-1<=n; i++)
{
for (int j=1; j+y-1<=m; j++)
{
ans=sum(i+x-1,j+y-1)-sum(i-1,j+y-1)-sum(i+x-1,j-1)+sum(i-1,j-1);
if (Max<ans) max="ans;" pre="" printf="" return=""><p>
</p>
</ans)></cstring></cstdio></iostream>
