C++前綴和

個人主頁：[PingdiGuo_guo]

收錄專欄：[C++干貨專欄]

大家好，今天我們來了解一下C++的一個重要概念：前綴和

1.什么是前綴和

2.前綴和的用法

1.前綴和的定義

2.預處理前綴和數組

3.查詢區間和

4.數組中某個區間的和是否為特定值

5.數組中連續子數組的和的最大值

6.數組中連續子數組的和的最小值

7.舉例

3.總結

1.什么是前綴和

C++前綴和是一種常用的算法，用于解決求解區間和問題。前綴和數組是一個長度為n的數組，其中第i個元素代表原始數組從下標0到下標i的元素之和。通過預先計算前綴和數組，可以在O(1)的時間復雜度內求解任意區間的和。

前綴和算法的基本思想是利用動態規劃的思想，通過累加計算出每一個位置的前綴和。具體實現時，可以對原始數組進行一次遍歷，累加計算出前綴和數組的每一個元素。

2.前綴和的過程

1.文字

前綴和它的基本思想是通過提前計算數組的前綴和，可以在O(1)的時間復雜度內求解任意子數組的和。下面我用文字詳細描述前綴和的過程，并用表格舉例演示。

1. 首先，我們定義一個數組，假設數組為arr，長度為n。我們需要額外定義一個長度為n+1的數組prefix_sum，用于存儲arr數組的前綴和。

2. 計算前綴和的過程如下：
? ?- 首先，初始化prefix_sum[0]為0，表示arr的前0個元素的和為0。
? ?- 然后，從1開始遍歷數組arr，逐個計算每個位置的前綴和，即prefix_sum[i] = prefix_sum[i-1] + arr[i-1]。

3. 最終，prefix_sum中存儲了arr數組的前綴和，prefix_sum[i]表示arr前i個元素的和。

2.圖示

下面通過一個具體的例子來說明前綴和的計算過程：

假設arr = [1, 2, 3, 4, 5]，長度為5，我們要計算其前綴和。

| arr索引 | 元素值 | 前綴和計算過程 ? ? ? ? ? | prefix_sum值 |
|---------|--------|-------------------------|--------------|
| 0 ? ? ? | 1 ? ? ?| prefix_sum[0] = 0 + 1 ? ?| 1 ? ? ? ? ? ?|
| 1 ? ? ? | 2 ? ? ?| prefix_sum[1] = 1 + 2 ? ?| 3 ? ? ? ? ? ?|
| 2 ? ? ? | 3 ? ? ?| prefix_sum[2] = 3 + 3 ? ?| 6 ? ? ? ? ? ?|
| 3 ? ? ? | 4 ? ? ?| prefix_sum[3] = 6 + 4 ? ?| 10 ? ? ? ? ? |
| 4 ? ? ? | 5 ? ? ?| prefix_sum[4] = 10 + 5 ? | 15 ? ? ? ? ? |

通過這個表格，我們可以看到prefix_sum數組中存儲了arr數組的前綴和。這樣，在求解任意子數組的和時，只需要通過prefix_sum數組中的值進行簡單的減法運算即可，實現了高效的求解過程。

3.前綴和的用法

C++前綴和是指在一個數組中，計算從數組起始位置到當前位置的所有元素的和。它的用途是在一些需要頻繁查詢某個區間和的場景中，可以通過預處理數組得到前綴和數組，從而在O(1)的時間復雜度內得到任意區間的和。

前綴和的用法可以分為以下幾點：

1.前綴和的定義

在C++中，可以使用一個額外的數組來保存原始數組中每個位置的前綴和，即累加前面所有元素的和。下面是一個示例代碼：

#include <iostream>
#include <vector>using namespace std;vector<int> prefixSum(vector<int>& nums) {int n = nums.size();vector<int> prefix(n);prefix[0] = nums[0]; ?// 第一個元素的前綴和就是其本身// 計算前綴和for (int i = 1; i < n; i++) {prefix[i] = prefix[i-1] + nums[i];}return prefix;
}int main() {vector<int> nums = {1, 2, 3, 4, 5};vector<int> prefix = prefixSum(nums);for (int num : prefix) {cout << num << " ";}cout << endl;return 0;
}

上述代碼中，prefixSum函數接受一個整型數組作為參數，并返回一個新的數組，其中保存了每個位置的前綴和。

在prefixSum函數中，首先創建了一個與原始數組大小相同的prefix數組，用于保存前綴和。然后，對于數組中的每個元素，通過累加前面所有元素的和來計算當前位置的前綴和。最后，返回計算得到的前綴和數組。

在main函數中，我們將一個示例數組傳入prefixSum函數，然后遍歷輸出計算得到的前綴和數組。

2.預處理前綴和數組

首先需要遍歷原始數組，計算出每個位置的前綴和，并將其存儲在一個新的數組中。具體的計算方法是，對于位置i，前綴和數組的第i個元素等于原始數組中前i個元素的和。

3.查詢區間和

一旦得到了前綴和數組，就可以通過查詢兩個位置的前綴和來計算任意區間的和。對于一個區間[a, b]，其和等于前綴和數組中第b個元素減去第a-1個元素（如果a不等于1）。

4.數組中某個區間的和是否為特定值

通過前綴和計算區間和后，可以用哈希表記錄出現的前綴和，以便在后續查詢中快速判斷。

5.數組中連續子數組的和的最大值

通過前綴和計算各個子數組的和，找出最大的子數組和。可以使用動態規劃或遍歷的方式實現。

6.數組中連續子數組的和的最小值

通過前綴和計算各個子數組的和，找出最小的子數組和。可以使用動態規劃或遍歷的方式實現。

7.舉例

假設有一個數組arr = {1, 2, 3, 4, 5}，我們可以通過預處理得到前綴和數組prefixSum = {1, 3, 6, 10, 15}。然后，我們可以通過查詢prefixSum - prefixSum[1-1]來計算區間[2, 4]的和，即6 - 1 = 5。

總結一下，C++前綴和的用法包括預處理前綴和數組和查詢區間和。通過預處理數組，可以在O(1)的時間復雜度內得到任意區間的和，從而提高了查詢效率。

4.用處

前綴和是一種常見的算法技巧，通常應用于數組相關的問題中。它的主要用途包括：

1. 快速計算數組區間和：通過預先計算數組的前綴和，可以在O(1)的時間復雜度內快速計算任意區間的和，而不需要每次都重新遍歷計算。

2. 解決子數組和為特定值的問題：通過計算前綴和，在一維數組中可以快速找到和為特定值的子數組。

3. 解決數組中連續子數組的最大和問題：通過計算前綴和，可以優化求解連續子數組的最大和問題，使得時間復雜度可以達到O(n)。

4. 解決求解區間和的問題：通過利用前綴和的特性，可以在較快的時間內解決求解多個區間和的問題。

5. 判斷兩個子數組是否具有相同的和：通過計算不同位置的前綴和，可以快速判斷兩個子數組是否具有相同的和，用于一些比較問題中。

總的來說，前綴和在解決數組相關問題時具有非常重要的作用，可以優化計算效率，減少時間復雜度。

5.例題

題目描述：
給定一個包含 n 個非負整數的數組 nums，一個連續子數組的最大和被定義為該子數組中所有正數的和。設計一個算法，計算出數組中連續子數組的最大和。例如，對于數組 [-2, 1, -3, 4, -1, 2, 1, -5, 4]，連續子數組的最大和為 6，對應子數組 [4, -1, 2, 1]。

限制：
- 數組中的元素個數 n 滿足 1 <= n <= 10^5
- 數組中的每個元素滿足 -1000 <= nums[i] <= 1000

分析步驟：
1. 使用前綴和的方法，定義一個一維數組 prefixSum，其中 prefixSum[i] 表示前 i 個元素的和。
2. 對于任意子數組 [i, j] 的和可以表示為 prefixSum[j] - prefixSum[i-1]。
3. 遍歷數組計算前綴和并更新最大子數組和，如果當前前綴和小于 0，則重新開始計算前綴和。
4. 最終，結果為更新過程中出現的最大子數組和。

代碼實現（C++）：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int maxSubarraySum(vector<int>& nums) {int n = nums.size();if (n == 0) return 0;vector<int> prefixSum(n);prefixSum[0] = nums[0];int maxSum = nums[0];for (int i = 1; i < n; i++) {prefixSum[i] = prefixSum[i-1] + nums[i];maxSum = max(maxSum, nums[i]);if (prefixSum[i] - prefixSum[i-1] > nums[i]) {prefixSum[i] = nums[i];}maxSum = max(maxSum, prefixSum[i]);}return maxSum;
}int main() {vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};cout << maxSubarraySum(nums) << endl; ?// 輸出 6return 0;
}