快捷導(dǎo)航

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

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

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

1.什么是前綴和

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

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

2.前綴和的過(guò)程

1.文字

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

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

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

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

2.圖示

下面通過(guò)一個(gè)具體的例子來(lái)說(shuō)明前綴和的計(jì)算過(guò)程：

假設(shè)arr = [1, 2, 3, 4, 5]，長(zhǎng)度為5，我們要計(jì)算其前綴和。

| arr索引 | 元素值 | 前綴和計(jì)算過(guò)程 | 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 |

通過(guò)這個(gè)表格，我們可以看到prefix_sum數(shù)組中存儲(chǔ)了arr數(shù)組的前綴和。這樣，在求解任意子數(shù)組的和時(shí)，只需要通過(guò)prefix_sum數(shù)組中的值進(jìn)行簡(jiǎn)單的減法運(yùn)算即可，實(shí)現(xiàn)了高效的求解過(guò)程。

3.前綴和的用法

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

前綴和的用法可以分為以下幾點(diǎn)：

1.前綴和的定義

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

#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];  // 第一個(gè)元素的前綴和就是其本身
    // 計(jì)算前綴和
    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ù)接受一個(gè)整型數(shù)組作為參數(shù)，并返回一個(gè)新的數(shù)組，其中保存了每個(gè)位置的前綴和。

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

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

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

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

3.查詢區(qū)間和

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

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

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

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

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

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

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

7.舉例

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

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

4.用處

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

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

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

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

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

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

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

5.例題

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

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

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

代碼實(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í)間復(fù)雜度分析：
- 遍歷數(shù)組一次，計(jì)算前綴和和更新最大子數(shù)組和，時(shí)間復(fù)雜度為 O(n)。
- 空間復(fù)雜度為 O(n)，用于存儲(chǔ)前綴和數(shù)組。

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