浅谈前缀和（一维）

Kingdom_Tears · 2025-08-12 21:48:18 · 算法·理论

前缀和的用途

前缀和是一种常用的算法技巧，通过预处理数组来快速计算某个区间的和。它的核心思想是利用空间换时间，预先计算出数组的前缀和，从而在查询时能够快速得到结果

一维前缀和的基本思想

一维前缀和的基本思想是构建一个新的数组 b ，其中 b_i 表示原数组从第 1 个元素到第 i 个元素的和。这样，在查询某个区间 [l, r] 的和时，时间复杂度为 O(1)

求前缀和数组

前缀和数组的第 i 项就是原数组从第 1 个元素到第 i 个元素的和，用代码写出来很简单

for (int i = 1; i <= n; i++){
   b[i] = b[i - 1] + a[i];
}

原数组 {a_i}=(0,1,2,3,4,5,6,7,8,9)

前缀和数组 {b_i}=(0,1,3,6,10,15,21,28,36,45)

前缀和求区间和的公式

求出了前缀和数组又怎样求一个区间的和呢？

我们假设这个区间是 [l, r]，原数组 a=(1,2,3,4,5) ，那么前缀和数组 b=(1,3,6,10,15) ，设 l=3 ，r=5 ，显而易见，区间和为 12 ，那怎么用代码写出来呢？我们可以用前 5 项的和减去前 2 项的和得到区间和，这与 l 和 r 有什么关系呢？我们发现 r 就等于 5 ，l-1 就等于 2 ，所以我们得出一个公式：

所以用代码写就是

int ans = b[r] - b[l - 1];//[l,r] 的区间和

一维前缀和最终代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, a[N], b[N], l, r;

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
        b[i] = b[i - 1] + a[i];//求前缀和数组
    }
    scanf("%d%d", &l, &r);
    int ans = b[r] - b[l - 1];//[l,r] 的区间和
    printf("%d", ans);

    return 0;
}