前缀和是指某序列的前n项和，可以把它理解为数学上的数列的前n项和，而差分可以看成前缀和的逆运算。合理的使用前缀和与差分，可以将某些复杂的问题简单化。

Login to join training plan

前缀和

先来了解这样一个问题：

输入一个长度为n的整数序列。接下来再输入m个询问，每个询问输入一对l, r。对于每个询问，输出原序列中从第l个数到第r个数的和。

我们很容易想出暴力解法，遍历区间求和。

const int N = 1e5 + 10;
int a[N];
int n,m;
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
while(m--)
{
    int l, r;
    int sum = 0;
    scanf("%d%d", &l, &r);
    for(int i = l; i <= r; i++)
    { 
        sum += a[i];
    }
    printf("%d\n",sum);
}

这样的时间复杂度为O(n * m)，如果n和m的数据量稍微大一点就有可能超时，而我们如果使用前缀和的方法来做的话就能够将时间复杂度降到O(n + m)，大大提高了运算效率。

具体做法：

首先做一个预处理，定义一个sum[]数组，sum[i]代表a数组中前i个数的和。

求前缀和运算：

const int N = 1e5 + 10;
int sum[N], a[N]; //sum[i]=a[1]+a[2]+a[3].....a[i];
for(int i = 1;i <= n; i++)
{ 
    sum[i] = sum[i - 1] + a[i];   
}

然后查询操作：

scanf("%d%d",&l,&r);
printf("%d\n", sum[r] - sum[l - 1]);

对于每次查询，只需执行sum[r] - sum[l - 1] ，时间复杂度为O(1)

原理:

$sum[r] = a[1] + a[2] + a[3] + a[l-1] + a[l] + a[l + 1] ...... a[r];$

$sum[l - 1] = a[1] + a[2] + a[3] + a[l - 1];$

$sum[r] - sum[l - 1] = a[l] + a[l + 1] + ......+ a[r];$

差分

解释

差分是一种和前缀和相对的策略，可以当做是求和的逆运算。

这种策略的定义是令 $b_i=\begin{cases}a_i-a_{i-1}\,&i \in[2,n] \\ a_1\,&i=1\end{cases}$

性质

*$a_i$ 的值是 $b_i$的前缀和，即 $a_n=\sum\limits_{i=1}^nb_i$

• 计算 $a_i$ 的前缀和$sum=\sum\limits_{i=1}^na_i=\sum\limits_{i=1}^n\sum\limits_{j=1}^{i}b_j=\sum\limits_{i}^n(n-i+1)b_i$

它可以维护多次对序列的一个区间加上一个数，并在最后询问某一位的数或是多次询问某一位的数。注意修改操作一定要在查询操作之前。

譬如使 $[l,r]$ 中的每个数加上一个 $k$，即

$b_l \leftarrow b_l + k,b_{r + 1} \leftarrow b_{r + 1} - k$

其中 $b_l+k=a_l+k-a_{l-1}$，$b_{r+1}-k=a_{r+1}-(a_r+k)$

最后做一遍前缀和就好了。

前缀和算法

前缀和算法是一种利用数组计算序列和的算法。该算法的前置知识是“满足结合律的加法运算”。

算法思路

假设有一个长度为 $n$ 的数组 $a$，预处理它的前缀和数组 $p$，则 $p$ 数组的下标范围为 $[0, n]$。它满足 $p[i] = \sum\limits_{j=0}^{i-1} a[j]$。也就是说，计算前缀和数组中的 $p_i$，我们需要从 $a$ 数组的第一个元素开始，一直加到第 $i-1$ 个元素，将这 $i-1$ 个元素的和赋值给 $p_i$。

例如，给出数组 $a = [1, 2, 3, 4, 5]$，则计算前缀和数组 $p$ 的过程如下：

$$\begin{aligned} p[0] &= 0, \\ p[1] &= a[0], \\ p[2] &= a[0] + a[1], \\ p[3] &= a[0] + a[1] + a[2], \\ p[4] &= a[0] + a[1] + a[2] + a[3], \\ p[5] &= a[0] + a[1] + a[2] + a[3] + a[4]. \\ \end{aligned}$$

$p$ 数组中 $p_i$ 的含义是从数组 $a$ 的下标 $0$ 开始，一直到下标 $i-1$ 的这一段区间的和。

计算前缀和数组 $p$ 可以使用循环，时间复杂度为 $O(n)$。根据前缀和数组 $p$，我们可以给出区间 $[l,r]$ 的和 $sum$ 的简单计算式：

$$sum = p[r+1] - p[l]$$

算法实现

数组实现的前缀和算法比较直观：首先定义一个数组 $a$，然后再定义一个与其长度相等的数组 $p$，最后循环计算 $p$ 数组的前缀和即可。

以下是 C++ 代码：

#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int a[N], p[N];

int main() {
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < n; i++) cin >> a[i];

    for (int i = 1; i <= n; i++) p[i] = p[i - 1] + a[i - 1];

    while (m--) {
        int l, r;
        cin >> l >> r;

        cout << p[r] - p[l - 1] << endl;
    }

    return 0;
}

算法优化

优化前缀和暴力循环的时间复杂度，可以通过以下的方法实现：

将原序列的前缀和计算结果存储在数组 $s$ 中。容易发现，前缀和的递推式为：$s_i = s_{i - 1} + a_i$。下标 $0$ 处用于边界条件，即 $s_0 = 0$。

可以证明，区间 $[l,r]$ 的和就是 $s_r - s_{l - 1}$。

计算前缀和时，可以使用前缀和数组 $s$：$s_i = s_{i - 1} + a_{i - 1}$。容易证明，这种方式等价于上述的定义。

以下是优化后的 C++ 代码：

#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int a[N], s[N];

int main() {
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < n; i++) cin >> a[i];

    for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i - 1];

    while (m--) {
        int l, r;
        cin >> l >> r;

        cout << s[r] - s[l - 1] << endl;
    }

    return 0;
}

注意，数组 $a$ 和 $s$ 的下标从 $0$ 开始，而数组 $p$ 的下标从 $1$ 开始。

算法应用举例

1. LeetCode 303. Range Sum Query - Immutable

题目描述：

给定一个整数数组 $nums$，求出数组中下标 $i$ 到 $j$ 的区间和。

解题思路：

预处理出前缀和数组 $p$，则区间 $[i, j]$ 的和为 $p[j+1]-p[i]$。

C++ 实现：

class NumArray {
public:
    NumArray(vector<int>& nums) {
        n = nums.size();
        s[0] = 0;
        for (int i = 0; i < n; i++) {
            s[i + 1] = s[i] + nums[i];
        }
    }

    int sumRange(int i, int j) {
        return s[j + 1] - s[i];
    }

private:
    const int N = 1e4 + 10;
    int s[N];
    int n;
};

2. AT3733 [AGC011B] Colorful Creatures

题目描述：

给定一个长度为 $n$ 的正整数数组 $a_{1\sim n}$，找到一种划分方法使得每一个子区间中，最大值的值都不超过这个子区间中元素数量的 $k$ 倍。输出划分方案，若有多组输出任意一组即可。若无解输出 $-1$。

解题方法：

首先将数组 $a$ 排序。对于数组中的单个元素来说，它同样也是一个合法的子区间。因此，我们可以将所有的元素先单独划为一组。接下来，从左往右扫描数组，将区间 $[l, r]$ 向右扩展时，只要 $a[r+1]\leq k(r-l+2)$，就将区间 $[l, r+1]$ 加入新的子区间中；否则，将区间 $[r+1,r+1]$ 单独划分为一组。

前缀和实现：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

int n, k;
int a[N], s[N];

int main() {
    cin >> n >> k;

    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a, a + n);

    memset(s, -1, sizeof s);
    s[0] = 0;
    int cnt = 1;

    for (int l = 0, r = 0; r < n; r++) {
        while (l < r && a[r] > k * (r - l + 1)) l++;

        if (s[cnt - 1] == r) s[cnt] = r + 1;
        else s[cnt] = r, cnt++;
    }

    if (s[cnt - 1] == n - 1) {
        cout << cnt << endl;
        for (int i = 1; i < cnt; i++) {
            cout << s[i] - s[i - 1] << " ";
        }
        cout << n - s[cnt - 1] << endl;
    } else {
        cout << -1 << endl;
    }

    return 0;
}

以上是前缀和算法的学习笔记，希望能为大家的学习提供一些帮助。