前綴和&差分

一維前綴和

對於資料做預處理，通常使用於求一個陣列區間的合。

以陣列v[n]={2,4,5,3,1,6}，六項(n=6)為例

1.先維護好一個陣列s[n]，s[i]=v[0]+v[1]+...v[i]
2.若要求v[a]到v[b]的總和(a<b)，求s[b]-s[a-1](差分)即可

這就是級數的概念，如果要求v[a]，也可寫成s[a]-S[a-1]，但其實沒必要

#include<bits/stdc++.h>
using namespace std;
int main(){
    int v[6]={2,4,5,3,1,6};
    int s[6];

    s[0]=v[0];
    for(int i=1;i<6;i++){
        s[i]=s[i-1]+v[i];
    }
    cout<<s[5]; //總和
    cout<<endl;
    cout<<s[5]-s[2]; //第4~6項總和
}

21
10

如果題目需要計算雙邊，可以建立兩個陣列雙向使用，沒有一定要是左向右，可以看到習題Q-1-4. 支點切割 (APCS201802) (@@)

二維前綴和

題目：b840: 104北二4.農作物採收問題

資料來源

alt text

相加程式

#include <bits/stdc++.h>
using namespace std;
#define N 22
#define nn "\n"
//istream& ss=cin;
stringstream ss("5 \
6 3 4 8 9 \
4 7 8 1 5 \
2 4 7 8 1 \
5 4 8 8 9 \
5 4 7 4 1 ");
int ve[N][N];
int v(int x,int y){
    if(x<0 || y<0){
        return 0;
    }
    return ve[x][y];
}
int main(){
    int n;
    ss>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            ss>>ve[i][j];
            ve[i][j]+=v(i-1,j)+v(i,j-1)-v(i-1,j-1);
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cout<<ve[i][j]<<" ";
        }
        cout<<nn;
    }
}

alt text

可以看到A(所求)=E-C-B+D
這就是二維前綴和的用法

例題：Q-6-5. 二維最大子矩陣

參考資料
https://hackmd.io/@SCIST/BytcSI9qd#UVa-108
buttom up

#include<bits/stdc++.h>
using namespace std;
int main(){
   int n,m;
   cin>>n>>m;
   vector<vector<int>>dp(n+1,vector<int>(m+1));
   vector<vector<int>>v(n+1,vector<int>(m+1));
   for(int i=1;i<=n;i++){
       for(int j=1;j<=m;j++){
           cin>>v[i][j];
       }
   }
   for(int i=1;i<=m;i++){
       dp[1][i]=v[1][i];
   }
   for(int i=1;i<=m;i++){
       for(int j=2;j<=n;j++){
           dp[j][i]=dp[j-1][i]+v[j][i];
       }
   }
   int ma=dp[n][m];//全部
   for(int i=1;i<=n;i++){
       for(int j=0;j<i;j++){
           int sum=0;
           for(int k=1;k<=m;k++){
               sum=max(0,sum+(dp[i][k]-dp[j][k]));
               ma=max(sum,ma);
           }
       }
   }
   cout<<ma;
   return 0;
}