👦個(gè)人主頁：Weraphael
?🏻作者簡介：目前正在學(xué)習(xí)c++和算法
??專欄：【C/C++】算法
🐋 希望大家多多支持，咱一起進(jìn)步！😁
如果文章有啥瑕疵
希望大佬指點(diǎn)一二
如果文章對你有幫助的話
歡迎 評論💬 點(diǎn)贊👍🏻 收藏 📂 加關(guān)注😍

---

一、一維前綴和

1.1 什么是一維前綴和

前綴和就是新建一個(gè)數(shù)組，數(shù)組中保存的是原數(shù)組前n項(xiàng)的和

【舉個(gè)例子】

• S_n = a₁+a₂+a₃+…a_n， S_n就是數(shù)列的前綴和（下標(biāo)一定要從1開始，后面會(huì)講解原因）

1.2 如何求Sn

我們可以利用上面的圖來找找規(guī)律

• S₁ = a₁
• S₂ = a₁ + a₂ = S₁ + a₂
• S3 = a₁ + a₂ + a₃ = S₂ + a₃
• S₄ = a₁ + a₂ + a₃ + a₄ = S₃ + a₄
• S₅ = a₁ + a₂ + a₃ + a₄ + a₅ = S₄ + a₅
• 這一套下來，前綴和的公式很明顯就是：S_i = S_i-1 + a_i

【代碼】

for (int i = 1;i <= n;i++)
{s[i] = s[i-1] + a[i];
}

1.3 用途

能快速求出數(shù)列中某一段的和，時(shí)間復(fù)雜度為O(1)

還是要利用這幅圖

假設(shè)我們要計(jì)算原數(shù)組a中區(qū)間[2,4]的和，我們就可以用S₄ - S₁，

• 總結(jié)：假設(shè)日后題目要求區(qū)間[l,r]的和，其實(shí)也能循環(huán)遍歷，不過時(shí)間復(fù)雜度是O(N)，而前綴和的時(shí)間復(fù)雜度是O(1)
• 計(jì)算區(qū)間[l,r]的和，其公式為S_r - S_l-1

1.4 代碼模板

#include <iostream>
using namespace std;const int N = 100010;
int a[N],s[n];int main()
{int n; //n - 原數(shù)組元素的個(gè)數(shù)scanf("%d",&n);//輸入原數(shù)組for (int i = 1;i <= n;i++) {scanf("%d",&a[i]);}//前綴和公式for (int i = 1;i <= n;i++){s[i] = s[i - 1] + a[i];}//以下是計(jì)算某段區(qū)間的和int l,r;scanf("%d%d",&l,&r);printf("%d\n",s[r] - s[l - 1]);return 0;
}

1.5 細(xì)節(jié)問題

• 首先，下標(biāo)從1開始就是為了定義S₀，就拿前綴和公式來說，S[i] = S[i-1] + a[i]，當(dāng)i = 1時(shí)，出現(xiàn)了S₀，而S₀要及時(shí)置為0，原因是為了統(tǒng)一。舉個(gè)例子，假設(shè)要計(jì)算區(qū)間[1,10]之間的和，明眼就能看出是要計(jì)算S₁₀，而為了達(dá)到統(tǒng)一計(jì)算的效果，S₁₀ - S₀ = S₁₀ - 0.
• 為什么我在代碼中沒有定義S[0]=0，原因是我將s[N]定成了全局變量，而全局變量有一個(gè)特點(diǎn)：默認(rèn)初始化為0！

二、二維前綴和

2.1 用途

目的是求出一個(gè)矩陣中某一個(gè)小矩陣的和

2.2 前綴和S[i][j]求法

大家畫圖可能會(huì)更加容易理解點(diǎn)，假設(shè)點(diǎn)（i，j）在矩陣的正中心，S[i][j] 即為黃色部分所有數(shù)的的和

我們可以分三步求出黃色部分的和

• 第一步先求出紅色部分所有數(shù)的和

列出式子：S[i][j] = S[i][j-1] + ...

• 第二步再求出綠色部分所有數(shù)的和

列出式子：S[i][j] = S[i][j-1] + S[i-1][j] + ...

• 第三步去重，因?yàn)榍皟刹恐貜?fù)加上了黑色部分所有數(shù)的和，因此要減掉一次

最后別忘了加上了本身：a[i][j]
列出式子：S[i][j] = S[i][j-1] + S[i-1][j] - S[i-1][j-1] + a[i][j]

2.3 子矩陣求法

假設(shè)要求左上角為（x1，y1），右下角為（x2，y2）所圍成黃色部分所有數(shù)的和

子矩陣的求法和求S[i][j]是類似的，四步走

• 第一步，先求出紅色部分圍成所有數(shù)的和

列出式子：S = S[x2][y2] - ...

• 第二步，在用上一步紅色部分減去綠色部分所有數(shù)的和

列出式子：S = S[x2][y2] - S[x1 - 1][y2] - ...

• 第三步，再減去灰色部分所有數(shù)的和

列出式子：S = S[x2][y2] - S[x1 - 1][y2] - S[x2][y1 - 1] + ...

• 第四步去重，因?yàn)榍皟刹恐貜?fù)減去了紫色部分所有數(shù)的和，因此要加上一次

列出式子：S = S[x2][y2] - S[x1 - 1][y2] - S[x2][y1 - 1] + S[x1 - 1][y1 - 1]

2.4 代碼模板

#include <iostream>
using namespace std;const int N = 10010;
int n, m;
int a[N][N],s[N][N];int main()
{scanf("%d%d%d", &n, &m); //n -行 m - 列//輸入數(shù)組for (int i = 1; i <= n; i ++ )for (int j = 1; j <= m; j ++ )scanf("%d", &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];//求子矩陣int x1, y1, x2, y2;scanf("%d%d%d%d", &x1, &y1, &x2, &y2);printf("%d\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);return 0;
}

三、總結(jié)

其實(shí)大家只要背下前綴和公式就好了

• 一維前綴和公式：S[i]= S[i-1] + a[i]
• 求某段區(qū)間[l,r]: S[r]- S[l-1]

---

• 二維前綴和公式：S[i][j] = S[i][j-1] + S[i-1][j] - S[i-1][j-1] + a[i][j]
• 求子矩陣公式：S = S[x2][y2] - S[x1 - 1][y2] - S[x2][y1 - 1] + S[x1 - 1][y1 - 1]