前缀和介绍

前缀和算法是一种优化技巧，常用于解决数组问题中的查询操作，例如区间求和、区间最大值/最小值等。其基本思路是先预处理出一个前缀和数组，在需要查询时通过计算前缀和数组的差值来得到查询结果。这个算法可以在O(1)的时间内回答很多查询问题，因此在实际编程中被广泛使用。

起源

前缀和算法的起源可以追溯到卡特兰数学家 Eugène Charles Catalan 在 1878 年提出的连续子序列问题。该问题要求在一个长度为 n 的数组中，找出所有连续子序列的和，并统计其中等于某个给定值的子序列的数量。Catalan 发现，如果先计算出数组的前缀和，则任意两个位置之间的子序列和可以通过前缀和数组的差值计算得出。通过这个思路，他成功地解决了这个问题，并将前缀和算法推广到更广泛的应用领域。

用法

前缀和算法是一种常用于数组问题的优化技巧，可以在O(1)的时间内回答很多查询问题，例如区间求和、区间最大值/最小值等。

C语言前缀和算法的基本思路是：先预处理出一个前缀和数组 prefix_sum，其中 prefix_sum[i] 表示原始数组 nums 的前 i 个元素的和；然后在需要查询时，通过计算 prefix_sum 的差值来得到查询结果。

代码

#include <stdio.h>
const int MAXN = 100005;
int nums[MAXN], prefix_sum[MAXN];
int main() {
    int n;
    scanf("%d", &n);
    // 输入原始数组
    for (int i = 1; i <= n; i++) {
        scanf("%d", &nums[i]);
    }
    // 预处理前缀和数组
    for (int i = 1; i <= n; i++) {
        prefix_sum[i] = prefix_sum[i-1] + nums[i];
    }
    // 查询区间 [l, r] 的和
    int l, r;
    scanf("%d %d", &l, &r);
    printf("区间 [%d, %d] 的和为：%d\n", l, r, prefix_sum[r] - prefix_sum[l-1]);
    return 0;
}

解析

上述代码中，我们首先定义了一个长度为 MAXN 的整型数组 nums 和 prefix_sum，其中 nums 存储原始数组，prefix_sum 存储前缀和数组。在主函数中，我们先读入原始数组 nums，并且计算出前缀和数组 prefix_sum。这里需要注意的是，为了方便计算，我们将 prefix_sum[0] 初始化为 0，这样求解 prefix_sum[i] 就不需要判断 i 是否等于 0。

在查询区间 [l, r] 的和时，我们可以直接用 prefix_sum[r] - prefix_sum[l-1] 计算出答案。这个式子的意思是，区间 [l, r] 的和等于前 r 个元素的和 prefix_sum[r] 减去前 l-1个元素的和 prefix_sum[l-1]。由于 prefix_sum[0] 已经预处理为 0，所以我们可以使用 prefix_sum[l-1] 而不必担心越界问题。

除了求和之外，前缀和算法还可以用来回答很多其他类型的查询问题，例如查询区间最大值/最小值、统计区间内元素个数等。通过巧妙地设计前缀和数组，我们可以在O(n)的时间内预处理出所有需要查询的结果，在O(1)的时间内回答每次查询，从而大大提高程序的效率。