腳本之家服務器常用軟件

快捷導航

C++前綴和及用法示例詳解

更新時間：2025年03月31日 09:14:08 作者：PingdiGuo_guo

前綴和算法的基本思想是利用動態(tài)規(guī)劃的思想,通過累加計算出每一個位置的前綴和,具體實現(xiàn)時,可以對原始數(shù)組進行一次遍歷,累加計算出前綴和數(shù)組的每一個元素,這篇文章主要介紹了C++前綴和的相關(guān)知識,需要的朋友可以參考下

1.什么是前綴和

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

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

2.前綴和的過程

1.文字

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

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

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

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

2.圖示

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

假設(shè)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數(shù)組中存儲了arr數(shù)組的前綴和。這樣，在求解任意子數(shù)組的和時，只需要通過prefix_sum數(shù)組中的值進行簡單的減法運算即可，實現(xiàn)了高效的求解過程。

3.前綴和的用法

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

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

1.前綴和的定義

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

#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函數(shù)接受一個整型數(shù)組作為參數(shù)，并返回一個新的數(shù)組，其中保存了每個位置的前綴和。

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

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

2.預處理前綴和數(shù)組

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

3.查詢區(qū)間和

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

4.數(shù)組中某個區(qū)間的和是否為特定值

通過前綴和計算區(qū)間和后，可以用哈希表記錄出現(xiàn)的前綴和，以便在后續(xù)查詢中快速判斷。

5.數(shù)組中連續(xù)子數(shù)組的和的最大值

通過前綴和計算各個子數(shù)組的和，找出最大的子數(shù)組和?？梢允褂脛討B(tài)規(guī)劃或遍歷的方式實現(xiàn)。

6.數(shù)組中連續(xù)子數(shù)組的和的最小值

通過前綴和計算各個子數(shù)組的和，找出最小的子數(shù)組和?？梢允褂脛討B(tài)規(guī)劃或遍歷的方式實現(xiàn)。

7.舉例

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

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

4.用處

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

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

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

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

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

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

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

5.例題

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

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

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

代碼實現(xiàn)（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;  // 輸出 6
    return 0;
}

時間復雜度分析：
- 遍歷數(shù)組一次，計算前綴和和更新最大子數(shù)組和，時間復雜度為 O(n)。
- 空間復雜度為 O(n)，用于存儲前綴和數(shù)組。

這道題目利用前綴和的方法可以較為簡潔地解決，但需要對連續(xù)子數(shù)組的性質(zhì)有一定的理解和分析，算法的設(shè)計相對較難一些。