CSP-J 算法基础 前缀和与差分

前言

在计算机科学中，处理数组的区间操作是一个常见的任务。无论是计算子数组的和，还是在数组的某个范围内应用加法操作，传统方法往往效率较低。为了提高处理这些问题的效率，前缀和（Prefix Sum）和差分（Difference Array）技术被广泛应用。它们不仅能够优化计算时间，还能简化代码实现。这些算法基础在解决许多实际问题时显得尤为重要，特别是在处理大规模数据时。本文将简要介绍前缀和与差分的基本概念及其应用，帮助读者理解如何利用这些技术提高计算效率。

前缀和

前缀和 就像是你在做一个累加的游戏。如果你有一列数字，比如 [2, 3, 5, 7]，你先把这些数字加起来，每一步累加的结果叫做“前缀和”。

1. 第一位置的前缀和就是 2。
2. 第二位置的前缀和就是 2 + 3 = 5。
3. 第三位置的前缀和就是 2 + 3 + 5 = 10。
4. 第四位置的前缀和就是 2 + 3 + 5 + 7 = 17。

这样，如果你想知道从第2个数字到第4个数字的总和（即 3 + 5 + 7），你只需要用前缀和来计算：

• 先找出第4个位置的前缀和（17）。
• 再减去第1个位置的前缀和（2）。

结果是 17 - 2 = 15，就是 3 + 5 + 7 的总和。

反正他就是一个预处理的过程，让数组的一段数相加在运行过程中更快得到结果，而不用去遍历浪费时间

差分

差分 就像是在玩一个标记游戏，标记哪些地方需要改变。如果你有一个数列 [0, 0, 0, 0]，你想把第2到第3的位置的数字都增加 3。

1. 你先在第2个位置标记 +3，第4个位置标记 -3（因为我们要把改变的地方标记出来）。
2. 然后，当你把这些标记的效果加到原来的数列中时，第2到第3的位置都增加了 3。

具体来说：

• 第2个位置 0 变成了 0 + 3 = 3。
• 第3个位置 0 变成了 0 + 3 = 3。
• 第4个位置变回了 0 - 3 = -3，其实这个是为了清除标记的影响。

所以差分就是用来快速标记和处理一段区间内的变化，之后再计算出最终的结果。

反正差分就是用来快速改变数组一段内容的算法

具体代码实现

前缀和

计算前缀和保存到一个数组中

计算前缀和我们需要把每一段计算的结果放到数组的每个元素中

1. 第一位置的前缀和就是 2。放到元素0中
2. 第二位置的前缀和就是 2 + 3 = 5。放到元素1中
3. 第三位置的前缀和就是 2 + 3 + 5 = 10。放到元素2中
4. 第四位置的前缀和就是 2 + 3 + 5 + 7 = 17。放到元素3中

那么我们如何实现他呢?
首先我规定，要计算前缀和的数组叫A，前缀和数组为B

我们直接把A数组元素1复制到B数组中，然后使用for循环进行循环相加
因为现需要计算的元素，他只需要把B数组前一个元素加上我们A数组中新加的元素即可

那么我们可以实现下面这个函数

// 函数：计算前缀和
void computePrefixSum(int arr[], int prefixSum[], int n) {
    // 计算第一个前缀和
    prefixSum[0] = arr[0];
    printf("prefixSum[0] = %d\n", prefixSum[0]);

    // 计算其余的前缀和
    for (int i = 1; i < n; i++) {
        prefixSum[i] = prefixSum[i - 1] + arr[i];
        printf("Step %d: prefixSum[%d] = prefixSum[%d] + arr[%d] = %d + %d = %d\n", 
                i, i, i - 1, i, prefixSum[i - 1], arr[i], prefixSum[i]);
    }
}

实现函数计算数组一段的和

区间 [l, r] 的和：
sum(l, r) = prefixSum[r] - prefixSum[l - 1]（当 l > 0）
如果 l 是 0，则 sum(0, r) = prefixSum[r]

int rangeSum(int prefixSum[], int l, int r) {
    if (l == 0) {
        return prefixSum[r];
    } else {
        return prefixSum[r] - prefixSum[l - 1];
    }
}

差分

定义差分数组

定义差分数组时，你需要先把左边界标记为n然后把右边界+1元素标记为-n，然后你需要把不在边界的元素标记为0

从第二到第三个元素：

int diff[n] = {0, 5, 0, -5, 0}; // 差分数组

运用差分到需要的数组中

设：A数组为要进行差分的数组，B为标记数组

1. 复制B数组元素0到A数组中
2. arr[i] = arr[i - 1] + diff[i];运用此公式即可求解

void applyDifference(int arr[], int diff[], int n) {
    // 直接复制第一个元素
    arr[0] = diff[0];
    printf("arr[0] = %d\n", arr[0]);

    // 循环处理剩余元素
    for (int i = 1; i < n; i++) {
        arr[i] = arr[i - 1] + diff[i];
        printf("Step %d: arr[%d] = arr[%d] + diff[%d] = %d + %d = %d\n", 
                i, i, i - 1, i, arr[i - 1], diff[i], arr[i]);
    }
}

总体代码

#include <stdio.h>

// 函数：计算前缀和
void computePrefixSum(int arr[], int prefixSum[], int n) {
    // 计算第一个前缀和
    prefixSum[0] = arr[0];
    printf("prefixSum[0] = %d\n", prefixSum[0]);

    // 计算其余的前缀和
    for (int i = 1; i < n; i++) {
        prefixSum[i] = prefixSum[i - 1] + arr[i];
        printf("Step %d: prefixSum[%d] = prefixSum[%d] + arr[%d] = %d + %d = %d\n", 
                i, i, i - 1, i, prefixSum[i - 1], arr[i], prefixSum[i]);
    }
}

// 函数：查询区间和
int rangeSum(int prefixSum[], int l, int r) {
    if (l == 0) {
        return prefixSum[r];
    } else {
        return prefixSum[r] - prefixSum[l - 1];
    }
}

int main() {
    int arr[] = {2, 3, 5, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    int prefixSum[n];

    // 计算前缀和
    computePrefixSum(arr, prefixSum, n);

    // 查询区间和，例如：从索引1到索引3的和
    int l = 1, r = 3;
    printf("Sum from index %d to %d is %d\n", l, r, rangeSum(prefixSum, l, r));

    return 0;
}




#include <stdio.h>

void applyDifference(int arr[], int diff[], int n) {
    // 直接复制第一个元素
    arr[0] = diff[0];
    printf("arr[0] = %d\n", arr[0]);

    // 循环处理剩余元素
    for (int i = 1; i < n; i++) {
        arr[i] = arr[i - 1] + diff[i];
        printf("Step %d: arr[%d] = arr[%d] + diff[%d] = %d + %d = %d\n", 
                i, i, i - 1, i, arr[i - 1], diff[i], arr[i]);
    }
}

int main() {
    int n = 5;
    int arr[n];
    int diff[n] = {0, 5, 0, -5, 0}; // 差分数组

    applyDifference(arr, diff, n);

    // 打印最终数组
    printf("Final array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

总结

前缀和和差分是高效处理数组区间操作的两个重要技术。前缀和通过预先计算前缀和数组，使得在任何区间内的和可以在常数时间内获得，适用于需要频繁查询数组区间和的场景。差分数组则通过记录区间更新的信息，避免了每次更新时都遍历整个区间，从而在处理频繁区间更新的任务时提高了效率。掌握这两种技术可以显著提高处理数组操作的效率和程序的性能，对于解决实际问题和优化算法具有重要意义。