🍎 博客主頁：🌙@披星戴月的賈維斯
🍎 歡迎關注：👍點贊🍃收藏🔥留言
🍇系列專欄：🌙 藍橋杯
🌙我與殺戮之中綻放，亦如黎明的花朵🌙
🍉一起加油，去追尋、去成為更好的自己！
藍橋杯倒計時 45天

文章目錄

• 🍎、前綴和
• 🍎、例題分析
• • • • 🍇、[（AcWing）前綴和](https://www.acwing.com/problem/content/797/)
      • 🍇、[（AcWing）子矩陣的和](https://www.acwing.com/problem/content/798/) 二維前綴和
      • 🍇、[（AcWing）截斷數組](https://www.acwing.com/problem/content/description/3959/)
• 🍎、總結

提示：以下是本篇文章正文內容，下面案例可供參考

---

🍎、前綴和

🍉、前綴和的簡單概念

前綴和算法分為一維和二維，一維前綴和可以很快速的求序列中某一段的和。而二維前綴和可以快速求一個矩陣中某個子矩陣的和。

一維前綴和的圖解：

前綴和數組的計算方法：前綴和數組s[i]是由原數組a[i]遞推而來的
即：s[i] = s[i - 1] + a[i]

🍎、例題分析

🍇、（AcWing）前綴和

分析題意：每次詢問查詢的是原數組l - r區間內的和， 因此我們可以設置一個原數組a和一個前綴和數組

代碼示例：

#include<cstdio> #include<algorithm> #include<iostream> #include<cstring> using namespace std; const int N = 100010; int a[N];//原數組 int s[N];//前綴合數組 int n, m;int main () {cin >> n >> m;for(int i = 1; i <= n; i++) {scanf("%d", &a[i]);s[i] = s[i - 1] + a[i];}while(m --){int l , r;cin >> l >> r;printf("%d\n", s[r] - s[l - 1]);}return 0; }

解法2：因為本題不需要用到原數組a,則可以直接創建一個前綴和數組s,并且原數組a上 L - R 區間內的值就是前綴和數組 s[R] - s[L - 1];
代碼示例：

#include<iostream> #include<algorithm> #include<cstring> using namespace std; int m, n; int s[100010]; int main () {cin >> n >> m;for(int i = 1; i <= n; i++){scanf("%d", &s[i]);s[i] += s[i - 1];}while(m --){int ans = 0;int l, r;cin >> l >> r;ans = s[r] - s[l - 1];cout << ans << endl;}return 0; }

🍇、（AcWing）子矩陣的和 二維前綴和

圖解二維前綴和的公式


代碼示例：

#include<iostream> #include<cstring> #include<algorithm> using namespace std; const int N = 1010; 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++){scanf("%d", &a[i][j]);s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];//計算二維前綴和}while(q --){int x1, x2, y1, y2;//計算每一次結果cin >> x1 >> y1 >> x2 >> y2;int ans = s[x2][y2] - s[x1 -1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 -1];cout << ans << endl;}return 0; }

🍇、（AcWing）截斷數組

算法：前綴和 + 枚舉

**分析題意：枚舉第二刀i處。

代碼示例：

#include<iostream> #include<cstring> #include<algorithm> using namespace std; typedef long long LL; const int N = 100010; int n; int s[N]; int main () {cin >> n;for(int i =1; i <= n; i++){int x;scanf("%d", &x);s[i] = s[i - 1] + x; //處理前綴和數組s[i]}if(s[n] % 3) //提前判斷結束條件{cout << "0" << endl;return 0;}LL res = 0;//因為答案可能爆intfor(int i = 3, cnt = 0; i <= n; i++){if(s[i - 2] == s[n] / 3) cnt++;if(s[n] - s[i - 1] == s[n] / 3) res += cnt; //s[n] - s[i - 1]是計算i - n區間的總和}printf("%lld\n", res);return 0; }

---

🍎、總結

????本文簡要介紹了前綴和的簡要概念和幾道前綴和的經典例題，希望大家讀后能有所收獲！

總結

以上是生活随笔為你收集整理的【蓝桥杯每日一题】前缀和算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。