前綴和是對於數列的一種預處理
經過 O(n) 初始化過後可以在 O(1) 就取得 [a, b] 的區間和
一維前綴和#
要點#
功能
- query：查詢某範圍的區間和
觀念
一維前綴和就是將第 N 項的數字改為 N 之前的所有總和
之後每次進行查詢我們就只需要輸出第 b 項數字減去第 a - 1 項數字
為了避免 a - 1 會減到負數
我們需要將索引改成 1-based，並將第 0 項數字設為 0
實作#
陣列宣告
vector<int> v(n+1, 0);
資料輸入
for (int i = 1; i <= n; i++) {
cin >> v[i];
v[i] += v[i-1];
}
查詢
cin >> a >> b;
cout << v[b] - v[a-1];
二維前綴和#
要點#
v[i][j] 儲存左上 ( 0, 0 ) 右下 (i, j) 內的總和
剩下的交給圖來解釋
圖片引用自 這裡
實作#
宣告陣列
vector<vector<int>> v(row+1, vector<int>(col+1, 0));
資料輸入
for (int i = 1; i <= row; i++) for (int j = 1; j <= col; j++) {
cin >> v[i][j];
v[i][j] += v[i-1][j] + v[i][j-1] - v[i-1][j-1];
}
查詢
cin >> sx >> sy >> ex >> ey;
cout << v[ey][ex] - v[ey][sx-1] - v[sy-1][ex] + v[sy-1][sx-1];
範例#
int row, col;
cin >> row >> col;
vector<vector<int>> v(row+1, vector<int>(col+1, 0));
for(int i = 1; i <= row; i++) for (int j = 1; j <= col; j++) {
cin >> v[i][j];
v[i][j] += v[i-1][j] + v[i][j-1] - v[i-1][j-1];
}
int sx, sy, ex, ey;
cin >> sx >> sy >> ex >> ey;
cout << v[ey][ex] - v[ey][sx-1] - v[sy-1][ex] + v[sy-1][sx-1];
