二維前綴和

表示(0,0)到(X,Y)矩形(綠色部分)內所有數值和

建表

dp概念:

dp[x][y]=dp[x][y]+dp[x-1][y]+dp[x][y-1]-dp[x-1][y-1];
 綠  色    灰  色    紅  色      藍  色      黃  色   

紅色+紅色+藍色-黃色

查詢

設從(Sx,Sy)到(Ex,Ey)的矩形

其範圍 =

dp[Ex][Ey]-dp[Sx-1][Ey]-dp[Ex][Sy-1]+dp[Sx-1][Sy-1]
  紅  色      綠  色        藍  色        粉  色

紅色-紅色-藍色+粉色

Code

int n,m;
cin >> n >> m;
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        cin >> pre[i][j];
        pre[i][j]=pre[i][j]+pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1];
    }
}
int q;
cin >> q;
while(q--){
    int x1,x2,y1,y2;
    cin >> x1 >> y1 >> x2 >> y2;
    x1--,y1--;
    int ans=pre[x2][y2]-pre[x2][y1]-pre[x1][y2]+pre[x1][y1];
    cout << ans << '\n';
}
    

二維矩形總和最大值

一維DP的延伸

1. 再輸入的時候就建立每一行的前綴和表

for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        cin >> arr[i][j];
        arr[i][j]+=arr[i][j-1];
    }
}

2. 窮舉每行的區間和列數

for(int i=1;i<=n;i++){
    for(int j=i;j<=n;j++){  
        //窮舉行的左邊界及右邊界
        
        for(int k=1;k<=m;k++){  
            //窮舉列數
            ...
        }
    }
}

3. 利用一維連續元素最大合的dp概念延伸 : 因為i j已經決定好寬度了，就相當於一維的一個元素，接下來的k只要遍歷列就好了，當sum<0的時候就代表對未來的結果沒有幫助，就把sum設為0，如此一來就能找到矩形最大的和了。

for(int i=1;i<=n;i++){
    for(int j=i;j<=n;j++){
        int sum=0;
        for(int k=1;k<=m;k++){
            sum+=arr[k][j]-arr[k][i-1];
            if(sum>ans) ans=sum; 
            if(sum<0) sum=0;
        }
    }
}