---

前言

本章將深度剖析前綴和，以及總結(jié)前綴和模板。

前綴和是一種在算法和數(shù)據(jù)處理中的重要技巧，特別適合解決連續(xù)子數(shù)組求和的問題。通過構(gòu)建一個(gè)前綴和數(shù)組，我們可以快速查詢?nèi)我膺B續(xù)區(qū)間的和，從而在一定程度上優(yōu)化時(shí)間復(fù)雜度。

基本原理
前綴和的核心思想是預(yù)先計(jì)算數(shù)組的前綴和，使得區(qū)間求和可以在常數(shù)時(shí)間內(nèi)完成。假設(shè)有一個(gè)數(shù)組 ( arr )，其前綴和數(shù)組定義如下：

• 設(shè) ( prefix[i] ) 表示從數(shù)組起點(diǎn)到位置 ( i ) 的元素之和。
• 因此，前綴和數(shù)組 ( prefix ) 可以定義為：
  [
  prefix[i] = arr[0] + arr[1] + \dots + arr[i]
  ]

計(jì)算任意區(qū)間和 ( arr[l] + arr[l+1] + \dots + arr[r] ) 可以通過前綴和快速得到：
[
arr[l] + arr[l+1] + \dots + arr[r] = prefix[r] - prefix[l-1]
]
其中， ( prefix[r] ) 是從 ( arr[0] ) 到 ( arr[r] ) 的和，減去從 ( arr[0] ) 到 ( arr[l-1] ) 的和就得到了區(qū)間 ( [l, r] ) 的和。

例子
假設(shè)有數(shù)組 ( arr = [1, 2, 3, 4, 5] )，構(gòu)建前綴和數(shù)組 ( prefix ) 如下：

• ( prefix[0] = 1 )
• ( prefix[1] = 1 + 2 = 3 )
• ( prefix[2] = 1 + 2 + 3 = 6 )
• ( prefix[3] = 1 + 2 + 3 + 4 = 10 )
• ( prefix[4] = 1 + 2 + 3 + 4 + 5 = 15 )

那么，求區(qū)間和 ( arr[1] + arr[2] + arr[3] ) 就可以通過前綴和數(shù)組計(jì)算：
[
arr[1] + arr[2] + arr[3] = prefix[3] - prefix[0] = 10 - 1 = 9
]

時(shí)間復(fù)雜度

• 構(gòu)建前綴和數(shù)組的時(shí)間復(fù)雜度為 ( O(n) )，其中 ( n ) 是數(shù)組的長(zhǎng)度。
• 一旦構(gòu)建好前綴和數(shù)組，查詢?nèi)我鈪^(qū)間的和的時(shí)間復(fù)雜度為 ( O(1) )。

前綴和技術(shù)通常用于快速解決子數(shù)組求和、二維區(qū)域求和等問題。

---

一、一維前綴和模板

【模板】前綴和

#include <iostream>
using namespace std;
#include<vector>
typedef long long LL;int n,q;int main()
{cin >> n >> q;vector<LL> arr(n + 1);for (int i = 1; i <= n; i++){cin >> arr[i];}//定義前綴和數(shù)組vector<LL> dp(n + 1);for (int i = 1; i <= n; i++){dp[i] = dp[i - 1] + arr[i];}//使用前綴和數(shù)組while (q--){LL l, r;cin >> l >> r;cout << dp[r] - dp[l - 1] << endl;}return 0;
}

---

二、二維前綴和模板

【模板】二維前綴和

#include <iostream>
using namespace std;#include<vector>
typedef long long LL;int main()
{int n, m, q;cin >> n >> m >> q;//初始化原始數(shù)據(jù)vector<vector<LL>> arr(n + 1, vector<LL> (m + 1));for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){cin >> arr[i][j];}}//定義前綴和數(shù)組vector<vector<LL>> dp(n + 1, vector<LL> (m + 1));for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + arr[i][j] - dp[i - 1][j - 1];}}//使用前綴和數(shù)組while (q--){LL x1, y1, x2, y2;cin >> x1 >> y1 >> x2 >> y2;cout << dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1] << endl;}return 0;
}

---

三、尋找數(shù)組的中心下標(biāo)

尋找數(shù)組的中心下標(biāo)

算法思路：

根據(jù)中心下標(biāo)的定義，除中心下標(biāo)元素外，該元素左邊的「前綴和」應(yīng)等于右邊的「后綴和」。

• 因此，可以先預(yù)處理兩個(gè)數(shù)組，一個(gè)表示前綴和，另一個(gè)表示后綴和。
• 然后，用一個(gè) for 循環(huán)枚舉可能的中心下標(biāo)，判斷每個(gè)位置的前綴和和后綴和是否相等，如果相等，則返回該下標(biāo)。

class Solution {
public:int pivotIndex(vector<int>& nums) {int n = nums.size();//構(gòu)建前綴和vector<int> dp_first(n);dp_first[0] = 0;for (int i = 1; i < n; i++){dp_first[i] = dp_first[i - 1] + nums[i - 1];}//構(gòu)建后綴和vector<int> dp_end(n);dp_end[n - 1] = 0;for (int i = n - 2; i >= 0; i--){dp_end[i] = dp_end[i + 1] + nums[i + 1];}//使用前綴和for (int i = 0; i < n; i++){if (dp_first[i] == dp_end[i])return i;}return -1;}
};

---

四、除自身以外數(shù)組的乘積

除自身以外數(shù)組的乘積

算法思路：

題目要求不能使用除法，并要求在 $O(N)$ 時(shí)間復(fù)雜度內(nèi)完成，排除了暴力解法和計(jì)算數(shù)組乘積后除以單個(gè)元素的方法。

分析可知，每個(gè)位置的最終結(jié)果 ret[i] 可以分為兩部分：

1. 前綴積部分：nums[0] * nums[1] * ... * nums[i - 1]
2. 后綴積部分：nums[i + 1] * nums[i + 2] * ... * nums[n - 1]

可以利用前綴和的思想，定義兩個(gè)數(shù)組 post 和 suf，分別存儲(chǔ)兩部分信息：

1. post：表示 i 位置之前所有元素的前綴乘積，即 [0, i - 1] 區(qū)間的乘積。
2. suf：表示 i 位置之后所有元素的后綴乘積，即 [i + 1, n - 1] 區(qū)間的乘積。

最后，根據(jù) post 和 suf 計(jì)算出每個(gè)位置的最終結(jié)果。

class Solution {
public:vector<int> productExceptSelf(vector<int>& nums) {int n = nums.size();//構(gòu)建前綴積vector<int> dp_first(n);dp_first[0] = 1;for (int i = 1; i < n; i++){dp_first[i] = dp_first[i - 1] * nums[i - 1];}//構(gòu)建后綴積vector<int> dp_end(n);dp_end[n - 1] = 1;for (int i = n - 2; i >= 0; i--){dp_end[i] = dp_end[i + 1] * nums[i + 1];}//使用前后綴積vector<int> answer(n);for (int i = 0; i < n; i++){answer[i] = dp_first[i] * dp_end[i];}return answer;}
};

---

五、和為 K 的子數(shù)組

和為 K 的子數(shù)組

（將前綴和存入哈希表）：

算法思路：

設(shè) i 為數(shù)組中的任意位置，sum[i] 表示 [0, i] 區(qū)間內(nèi)所有元素的和。

• 我們需要找到“以 i 為結(jié)尾且和為 k 的子數(shù)組”，這等價(jià)于找出所有可能的起始位置 x1, x2, x3...，使得 [x, i] 區(qū)間的和為 k。
• 此時(shí)，[0, x] 區(qū)間的和應(yīng)為 sum[i] - k。

因此，問題轉(zhuǎn)化為：

• 找出 [0, i - 1] 區(qū)間內(nèi)有多少前綴和等于 sum[i] - k。

無需真正初始化前綴和數(shù)組，因?yàn)槲覀冎魂P(guān)注 i 位置之前，前綴和為 sum[i] - k 的次數(shù)。我們可以使用一個(gè)哈希表，在計(jì)算當(dāng)前位置的前綴和時(shí)，同時(shí)記錄每個(gè)前綴和出現(xiàn)的次數(shù)。

class Solution {
public:int subarraySum(vector<int>& nums, int k) {// 哈希表模擬前綴和數(shù)組unordered_map<int, int> hash;hash[0] = 1;//使用前綴和數(shù)組int sum = 0, ret = 0;for (auto e : nums){sum += e;if (hash.count(sum - k)) ret += hash[sum - k];hash[sum]++;}return ret;}
}; 

---

六、和可被 K 整除的子數(shù)組

和可被 K 整除的子數(shù)組



本題需要的前置知識(shí)：

• 同余定理：
  若 (a - b) % n == 0，則 a % n == b % n。也就是說，如果兩個(gè)數(shù)之差能被 n 整除，那么這兩個(gè)數(shù)對(duì) n 取模的結(jié)果相同。
  例如，(26 - 2) % 12 == 0，所以 26 % 12 == 2 % 12 == 2。

• C++ 中負(fù)數(shù)取模結(jié)果的處理：

  • 在 C++ 中，負(fù)數(shù)取模的結(jié)果會(huì)保留負(fù)號(hào)，例如 -1 % 3 = -1。
  • 為防止負(fù)數(shù)結(jié)果影響，常用 (a % n + n) % n 確保結(jié)果為正，例如：-1 % 3 = (-1 % 3 + 3) % 3 = 2。

算法思路：

此題與 LeetCode 560 題“和為 K 的子數(shù)組”思路類似。

設(shè) i 為數(shù)組中的任意位置，sum[i] 表示 [0, i] 區(qū)間內(nèi)的和。

• 要找出“以 i 為結(jié)尾、和可被 k 整除的子數(shù)組”，需要找到所有起點(diǎn) x1, x2, x3... 使得 [x, i] 的和能被 k 整除。
• 假設(shè) [0, x - 1] 的和為 a，[0, i] 的和為 b，則有 (b - a) % k == 0。
• 根據(jù)同余定理，[0, x - 1] 區(qū)間和 [0, i] 區(qū)間的前綴和同余。因此問題變成：
  • 找到 [0, i - 1] 中前綴和的余數(shù)等于 sum[i] % k 的個(gè)數(shù)。

無需初始化前綴和數(shù)組，只需用一個(gè)哈希表記錄每種前綴和的出現(xiàn)次數(shù)，同時(shí)計(jì)算當(dāng)前位置的前綴和。

class Solution {
public:int subarraysDivByK(vector<int>& nums, int k) {// 哈希表模擬前綴和數(shù)組unordered_map<int,int> hash;hash[0] = 1;//使用前綴和數(shù)組int sum = 0, ret = 0;for (auto e : nums){sum += e;int r = (sum % k + k) % k;if (hash.count(r)) ret += hash[r];hash[r]++;}return ret;}
};

---

七、連續(xù)數(shù)組

連續(xù)數(shù)組

算法思路：

稍作轉(zhuǎn)換，這道題可以化為經(jīng)典問題：

• 本題需要找一個(gè)連續(xù)區(qū)間，使得 0 和 1 出現(xiàn)的次數(shù)相同。
• 將 0 視為 -1，1 視為 1，問題就轉(zhuǎn)化為找一個(gè)區(qū)間，使其和等于 0。

這樣問題與 LeetCode 560 題“和為 K 的子數(shù)組”思路相似。

設(shè) i 為數(shù)組中任意位置，用 sum[i] 表示 [0, i] 區(qū)間內(nèi)所有元素的和。我們希望找到最大長(zhǎng)度的“以 i 為結(jié)尾、和為 0 的子數(shù)組”，這需要找到從左至右第一個(gè)位置 x1 使得 [x1, i] 的和為 0。此時(shí) [0, x1 - 1] 區(qū)間的和等于 sum[i]。因此問題變成：

• 找到 [0, i - 1] 區(qū)間內(nèi)首次出現(xiàn) sum[i] 的位置即可。

我們無需真正初始化一個(gè)前綴和數(shù)組，因?yàn)橹魂P(guān)心 i 位置之前，首次出現(xiàn)等于 sum[i] 的前綴和位置。只需一個(gè)哈希表，在計(jì)算當(dāng)前位置前綴和的同時(shí)，記錄該前綴和的首次出現(xiàn)位置。

class Solution {
public:int findMaxLength(vector<int>& nums) {// 哈希表模擬前綴和數(shù)組unordered_map<int, int> hash;hash[0] = -1; // 使用前綴和數(shù)組int sum = 0, ret = 0;for (int i = 0; i < nums.size(); i++){sum += nums[i] == 0 ? -1 : 1;if (hash.count(sum)) ret = max(ret, i - hash[sum]);else hash[sum] = i;}    return ret;}
};

---

八、矩陣區(qū)域和

矩陣區(qū)域和

算法思路：

這道題主要是二維前綴和的基本應(yīng)用，關(guān)鍵在于填寫結(jié)果矩陣時(shí)，找到原矩陣對(duì)應(yīng)區(qū)域的「左上角」和「右下角」坐標(biāo)（建議畫圖理解）。

• 左上角坐標(biāo)：x1 = i - k，y1 = j - k，為了不超出矩陣范圍，需要對(duì) 0 取 max，修正后的坐標(biāo)為：x1 = max(0, i - k)，y1 = max(0, j - k)。
• 右下角坐標(biāo)：x2 = i + k，y2 = j + k，同理，為避免超出矩陣范圍，需要對(duì) m - 1 和 n - 1 取 min，修正后的坐標(biāo)為：x2 = min(m - 1, i + k)，y2 = min(n - 1, j + k)。

最后將修正后的坐標(biāo)代入二維前綴和的計(jì)算公式即可（注意下標(biāo)的映射關(guān)系）。

class Solution {
public:vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {// 構(gòu)建二維前綴和int n = mat.size(), m = mat[0].size();vector<vector<int>> dp(n + 1, vector<int> (m + 1));for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + mat[i - 1][j - 1] - dp[i - 1][j - 1];}}   //使用二維前綴和vector<vector<int>> answer(n, vector<int> (m));for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){int a, b, c, d;a = i - k < 0 ? 1 : i - k + 1;b = j - k < 0 ? 1 : j - k + 1;c = i + k >= n ? n : i + k + 1;d = j + k >= m ? m : j + k + 1;answer[i][j] = dp[c][d] - dp[c][b - 1] - dp[a - 1][d] + dp[a - 1][b - 1];}}return answer;}
};

---