【算法 C/C++】一维前缀和

2025 - 03 - 08 - 第 68 篇
Author: 郑龙浩 / 仟濹
【一维前缀和】

前缀和与差分 - 我的博客

一维前缀和
【算法 C/C++】一维前缀和
一维差分
【算法 C/C++】一维差分
二维前缀和
【算法 C/C++】二维前缀和
二维差分
【算法 C/C++】二维差分# 前缀和(一维)

时间复杂度为 O(1)

可以在O(1)的时间复杂度内获取任意子数组的和。

1 大体介绍

是一种用于计算区间和的问题的高效算法，尤其适用于静态数组（即数组在查询时是不会改变的）。它通过预先计算前缀和数组来快速响应区间和查询，时间复杂度为 O(1)，空间复杂度为 O(n)，适用于多次查询的场景。

2 计算某些区间的和( 不使用前缀和 )

题目

有一个数组 arr[5] = {1, 3, 7, 5, 2}，求如下区间的和

[3, 4] [2, 4] [0, 3]？？

答案为：7 14 16

思路

如果不使用前缀和的话，会非常的麻烦，且如果求得区间非常多，且数值较大，时间复杂度会非常大。下面写的是不使用前缀和的时候的方法，纯循环。

代码

#include <algorithm>
#include <iostream>
using namespace std;
int arr[5] = {1, 3, 7, 5, 2};
int sum(int a, int b){
    int ans = 0;
    for( int i = a; i <= b; i++ ){
        ans += arr[ i ];
    }
    return ans;
}
int main( void ){
    cout << sum(3, 4) << " " << sum(2, 4) << " " << sum(0, 3) << endl;
    return 0;
}

3 计算某些区间的和( 使用前缀和 )

题目

有一个数组 arr[5] = {1, 3, 7, 5, 2}，求如下区间的和

[3, 4] [2, 4] [0, 3]？？

答案为：7 14 16

思路

提前写一个数组比如sum，在 sum[i] 中存储 sum[0]到sum[i] 的和。

前缀和的方法：当求某个区间比如 [2, 4] 的时候，只需要计算 [0, 4] 的和 - [0, 1] 的和，也就是 sum[4] - sum[1]

即，如果求[a, b]的和，只需要 sum[b] - sum[a - 1]

这样的好处是，当需要计算多个区间的时候，节省了计算时间，比如[a, b]，之前的方式是从 arr[a]循环累加到arr[b]，学习了前缀和以后无需这么麻烦，只需要提前将 arr[i]到arr[0]的和计算出来，当需要知道某个区间的和的时候，只需要进行不同位置的和的相减计算即可。

代码1 - 使用函数

// 使用前缀和计算区间
// 有一个数组 `arr[5] = {1, 3, 7, 5, 2}`，求如下区间的和
// `[3, 4] [2, 4] [0, 3]`？？
// 答案为：`7 14 16`
#include <algorithm>
#include <iostream>
using namespace std;
#define N 5
int arr[5] = {1, 3, 7, 5, 2};
int sum[5];
int get_sum(int a, int b){
    // 如果计算的是 [0, b]，直接打印 sum[b] 即可 --> sum[b] 就是 [0, b] 的和
    if( a == 0 ){
        return sum[ b ];
    } else {
        return sum[ b ] - sum[ a - 1 ];
    }
}
int main( void ){
    sum[ 0 ] = arr[ 0 ]; // 第一个元素到第一个元素的和为第一个元素
    for( int i = 1; i < N; i++ ){
        sum[ i ] = sum[i - 1] + arr[ i ];
    }
    cout << get_sum(3, 4) << " " << get_sum(2, 4) << " " << get_sum(0, 3) << endl;
    return 0;
}

代码2 - 使用字符串替换 #define

更简洁高效的代码

// 使用前缀和计算区间
// 有一个数组 `arr[5] = {1, 3, 7, 5, 2}`，求如下区间的和
// `[3, 4] [2, 4] [0, 3]`？？
// 答案为：`7 14 16`
#include <algorithm>
#include <iostream>
using namespace std;
#define get_sum(a, b) (a ? sum[b] - sum[a - 1] : sum[b])
#define N 5
int arr[5] = {1, 3, 7, 5, 2};
int sum[5];
int main( void ){
    sum[ 0 ] = arr[ 0 ]; // 第一个元素到第一个元素的和为第一个元素
    for( int i = 1; i < N; i++ ){
        sum[ i ] = sum[i - 1] + arr[ i ];
    }
    cout << get_sum(3, 4) << " " << get_sum(2, 4) << " " << get_sum(0, 3) << endl;
    return 0;
}