目錄
- 前綴和
- 一維前綴和
- Skips
- 模板題
- 代碼
- 二維前綴和
- Skips
- 模板題
- 代碼
前綴和
一維前綴和
Skips
-
快速計算一個區間內數的和 [l,r]
-
定義一個陣列 ，下標要從1 開始 ，邊界值 定義 s[0]=0 （如果是全域變數 的 陣列 不必再 初始化，若不是 記得初始化s[0]=0），記錄 s[i] 為 陣列 a 中第 i個數之前所有數的和
-
```s[i] = s[i-1] + a[i];// 遞推公式 這里面有 i-1 所以 當 l=1 的時候 （就是從第一個數開始算的話）`下標會為 i-1 那么i-1 就得是 0 不然數就不對 ``
-
具體計算 使用 是
s[r]-s[l-1]因為 s[]陣列記錄的是 多少個數 的和 相減 正好剩下 兩個下標相差的值 注意這里是l-1如果是 l 的話那么 剪完之后是 s[l+1] 到 s[r] 的值 中間a[l] 的在兩個前綴里面都有，就被減掉了，
模板題
輸入一個長度為n的整數序列，
接下來再輸入m個詢問，每個詢問輸入一對l, r，
對于每個詢問，輸出原序列中從第l個數到第r個數的和，
輸入格式
第一行包含兩個整數n和m，
第二行包含n個整數，表示整數數列，
接下來m行，每行包含兩個整數l和r，表示一個詢問的區間范圍，
輸出格式
共m行，每行輸出一個詢問的結果，
資料范圍
1≤l≤r≤n1≤l≤r≤n,
1≤n,m≤1000001≤n,m≤100000,
?1000≤數列中元素的值≤1000?1000≤數列中元素的值≤1000
輸入樣例：
5 3
2 1 3 6 4
1 2
1 3
2 4
輸出樣例：
3
6
10
代碼
#include<iostream>
using namespace std;
const int N=1e5+10;
int a[N],s[N]; // s[0]=0;
int n,m;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i]; //陣列 a存完之后 在 存s陣列
for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i]; // 遞推公式
while(m--)
{
int l,r;
cin>>l>>r;
cout<<s[r]-s[l-1]<<endl; // 輸出的時候下標 右端點 數值 減一
}
return 0;
}
二維前綴和
Skips
-
應用：
- 給出一個坐標，求出 以 該坐標為右下角的矩陣的元素的和
- 給出兩個坐標，求出 以 小的坐標為 左上角，大的坐標為右上角 的矩陣元素的和
-
核心
-
第一個應用 ： 求和 的具體操作
// 利用了容斥原理 通過 分塊的思想 // 先讀入元素 for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j]; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) /* 核心*/ s[i][j]= s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j]; // 加的時候 多加的 要減去 不要忘了 a[i][j] -
第二個應用： 做差 的具體操作
int x1,y1,x2,y2; cin>>x1>>y1>>x2>>y2; cout<<s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]<<endl; // 減的時候多 減了要加回來 return 0;
-
模板題
輸入一個n行m列的整數矩陣，再輸入q個詢問，每個詢問包含四個整數x1, y1, x2, y2，表示一個子矩陣的左上角坐標和右下角坐標，
對于每個詢問輸出子矩陣中所有數的和，
輸入格式
第一行包含三個整數n，m，q，
接下來n行，每行包含m個整數，表示整數矩陣，
接下來q行，每行包含四個整數x1, y1, x2, y2，表示一組詢問，
輸出格式
共q行，每行輸出一個詢問的結果，
資料范圍
1≤n,m≤10001≤n,m≤1000,
1≤q≤2000001≤q≤200000,
1≤x1≤x2≤n1≤x1≤x2≤n,
1≤y1≤y2≤m1≤y1≤y2≤m,
?1000≤矩陣內元素的值≤1000?1000≤矩陣內元素的值≤1000
輸入樣例：
3 4 3
1 7 2 4
3 6 2 8
2 1 2 3
1 1 2 2
2 1 3 4
1 3 3 4
輸出樣例：
17
27
21
代碼
#include<iostream>
using namespace std;
const int N=1e3+10;
int a[N][N],s[N][N];
int n,m,q;
int main()
{
cin>>n>>m>>q;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
while(q--)
{
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
cout<<s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]<<endl;
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/30654.html
標籤：C++
上一篇：博弈--尼姆博弈
下一篇：單調佇列模板【附例題】