一、考察频率以及难度
考察频率：⭐⭐⭐⭐⭐
笔试题难度：⭐⭐
算法难度：⭐
前缀和在笔试中占据着举足轻重的位置，其算法基础且简单，且有基于前缀和思想的多种变体，考察十分灵活，因此在笔试题中被出题者青睐，往往作为签到题或简单题出现，希望同学们务必掌握。
二、学习技巧

1. 熟练运用递推的思想，思考如何维护一个数组来满足相应的定义。

2. 举一反三，类似的思想如何应用于其他领域？
   

三、应用场景

1. 需要高效的区间查询场景（包括区间和，区间乘积，区间异或等）

2. 需要前缀、后缀等维护的情况

四、算法讲解

有n（n<1e5）个元素的数组a，给定l和r，要求输出a[l]+a[l+1]+...+a[r]这个区间和。

你会怎么思考呢？是不是直接for循环累加就可以了呢？现在把上题进阶一下如下：

有n（n<1e5）个元素的数组a，和q（q<1e5）次询问每次询问给定l和r，要求输出a[l]+a[l+1]+...+a[r]这个区间和。

对于进阶版本，按照原来的做法复杂度就变成O(nq)了，因此考虑优化。

4.1 一维前缀和

4.1.1 维护

对原数组a维护一个前缀和数组sum，定义为sum[i]代表前i值的和，示例如下：

a   = [1,2,3,4]
sum = [1,3,6,10]

根据定义不难发现一遍for循环就可以维护出sum数组，时间复杂度为O(n)，算法如下：

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

4.1.2 使用

有了维护出的sum数组，就可以在O(1)的时间复杂度内求出一段区间的和。

对于待求区间[L,R]，ans=a[l]+..+a[r] = a[1]+...+a[r] - (a[1]+...+a[l-1])=sum[r]-sum[l-1]，即可以把一段区间的和转化成两个前缀的差，算法代码如下：

int solve(int l, int r) {
    return sum[r]-sum[l-1];
}

至此，我们可以在O(1)时间内求解任意一段区间的和，因此该进阶版本题目的总复杂度降为O(n+q)，其中维护时间O(n)，求解成本O(q)。

该题目的完整解法如下：

#include<iostream>
int a[100005], sum[100005];
void init() {
    for(int i = 1; i<=n; i++) {
        sum[i] = sum[i-1]+a[i];
    } 
}
int solve(int l, int r) {
    return sum[r]-sum[l-1];
}

int main() {
    cin>>n>>q;
    for(int i = 1; i<=n; i++) cin>>a[i];
    init();// 维护
    while(q--) {
        int l,r;
        cin>>l>>r;
        cout << solve(l,r) << endl; // 使用
    }
}

4.2 二维前缀和

解决了上述问题，现在把问题扩展到二维，假设我们要求二维数组汇总，某一个子矩阵的和，应该怎么做呢？

相应的，定义二维数组sum[i][j]代表(1,1)到(i,j)的和,比如下图中，sum[2][3]就代表红色区域的元素和，那么如何维护sum以及使用sum来求任意一个矩形的元素和呢？

4.2.1 维护

假如我们用上图的星星格子代表下标(i,j)，则

sum[i][j] 
= 红+黄+绿+蓝 
= 蓝+（红+绿）+（红+黄）-红 
= a[i][j]+sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]

而递推公式中用到的值，都已经是在维护sum[i][j]之前求出过的值，因此公式是正确的（由已知推未知），因此对二维数组的维护算法如下：

void init() {
    for(int i = 1; i<=n; i++) {
        for(int j = 1; j<=m; j++) {
            sum[i][j] = a[i][j]+sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1];
        }
    }
}
    

4.2.2 使用

所谓使用，即求左上角为(i1, j1)到右下角(i2, j2)所围成的矩形的值的和，如下图，此时

ans = 蓝
    = (红+绿+黄+蓝) - (红+绿) - (红+黄) + 红
    = sum[i2][j2] - sum[i2][j1-1] - sum[i1-1][j2] + sum[i1-1][j1-1]

因此二维前缀和的使用算法如下：

int calc(int i1, int j1, int i2, int j2) {
    return sum[i2][j2] - sum[i2][j1-1] - sum[i1-1][j2] + sum[i1-1][j1-1]
}

五、例题与解析

5.1 基础-寻找团队中的关键人物

有一支队伍要评价一下自己队伍的战斗力，

现在有一支n个人的球队构成数组a，每个人都有自己的战斗力值，其中第i号球员的战力值为a[i]，已知球队的战斗力是球队中每个队员的战斗力值的乘积，现在管理层有q个询问，每次询问一个整数x，代表x号球员如果离队了，则团队中的战斗力有多少？对每次询问请输出战斗力对1e9+7取模后的值。（n,q<1e5, 0<a[i]<1e9）

输入
5 3
1 2 3 4 5
1
2
4
输出
120
60
30 

题解：类似前缀和的思想，维护前缀乘积L数组和后缀乘积R数组，维护时间复杂度O(n)。此时如果x号球员离队的话，即答案=L[x-1] * R[x+1]，求解复杂度O(1)。

C++

#include<iostream>
using namespace std;
const int MAX = 1e6 + 5;
const int mod = 1e9 + 7;
long long a[MAX], L[MAX], R[MAX];
int n,q;
int main()
{
    cin>>n>>q;
    for(int i = 1; i<=n; i++) scanf("%lld", a+i);
    L[0] = 1; R[n+1] = 1;
    for (int i = 1; i<=n; i++) {
        L[i] = a[i] * L[i - 1] % mod;
    }

    for (int i = n; i>=1; i--) {
        R[i] = a[i] * R[i + 1] % mod;
    }
    
    while(q--) {
        int x;
        scanf("%d", &x);
        printf("%lld\n",  L[x-1] * R[x+1] % mod);

    }
    return 0;
}

Java

import java.util.Scanner;

public class Main {
    private static int MAX = (int) 1e6 + 5;
    private static int mod = (int) 1e9 + 7;
    private static long[] a = new long[MAX], L = new long[MAX], R = new long[MAX];
    private static int n, q;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        q = sc.nextInt();
        for(int i = 1; i <= n; i++) {
            a[i] = sc.nextLong();
        }
        L[0] = 1; R[n+1] = 1;
        for (int i = 1; i <= n; i++) {
            L[i] = a[i] * L[i - 1] % mod;
        }

        for (int i = n; i >= 1; i--) {
            R[i] = a[i] * R[i + 1] % mod;
        }

        while (q-- > 0) {
            int x = sc.nextInt();
            System.out.println(L[x - 1] * R[x + 1] % mod);
        }
    }
}

Python

MAX = int(1e6) + 5
mod = int(1e9) + 7
a = [0] * MAX
L = [1] * MAX
R = [1] * MAX

n, q = map(int, input().split())
a = list(map(int, input().split()))
a.insert(0, 0)  # Since we start the index from 1

for i in range(1, n+1):
    L[i] = a[i] * L[i - 1] % mod

R.append(1)
for i in range(n, 0, -1):
    R[i] = a[i] * R[i+1] % mod  

for _ in range(q):
    x = int(input())
    print(int(L[x-1] * R[x+1] % mod))

5.2 基础-寻找最优解

小牛拿到一张有n（n<1e5）道题目的试卷，并且按照题目顺序做题，每个题都是判断题，有T/F两种选项，数组a便记录了小牛给出的答案。小牛有一张时光回溯卡，可以修改某一个时刻之前的所有答案变成相反的选项（T变F，F变T），现在小牛想知道自己最多能做对几道题目？（小牛可以选择不适用时光回溯卡）

输入
TTFFF
输出
3

题解：用前缀和sum[i]维护前i个题中做对的数量，然后枚举在哪个时刻使用时光回溯卡，当在第i个时刻使用时光回溯卡的时候，最多的题目数为i-sum[i] + (sum[n] - sum[i])。

代码：

C++

#include<iostream>
#include<cstring>
using namespace std;
const int MAX = 1e5 + 5;
int T[MAX],sum[MAX];
int n;
char s[MAX];
int main()
{
    cin>>s+1;
    n = strlen(s+1);
    for(int i = 1; i<=n; i++) {
        sum[i] = sum[i-1];
        if(s[i] == 'T') sum[i]++;
    }
    int ans = sum[n];
    //枚举在哪个时刻使用时光回溯卡
    for(int i = 1; i<=n; i++) {
        ans = max(ans, i-sum[i] + (sum[n] - sum[i]));
    }
    cout << ans << endl;
    return 0;
}

Java

import java.util.Scanner;

public class Main {
    private static final int MAX = (int) 1e5 + 5;
    private static int[] sum = new int[MAX];
    private static int n;
    private static String s;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        s = " " + scanner.nextLine();
        n = s.length() - 1;
        for (int i = 1; i <= n; i++) {
            sum[i] = sum[i - 1];
            if (s.charAt(i) == 'T') sum[i]++;
        }
        int ans = sum[n];
        for (int i = 1; i <= n; i++) {
            ans = Math.max(ans, i - sum[i] + (sum[n] - sum[i]));
        }
        System.out.print(ans);
    }
}

Python

MAX = int(1e5) + 5
sum = [0] * MAX

s = input()
s = " " + s
n = len(s) - 1
for i in range(1, n+1):
    sum[i] = sum[i - 1]
    if s[i] == 'T':
        sum[i] += 1
ans = sum[n]
for i in range(1, n + 1):
    ans = max(ans, i - sum[i] + (sum[n] - sum[i]))
print(ans)

5.3 基础-子数组的最大和

https://oj.niumacode.com/problem/P1410

给一个有正有负的数组，长度为n，问其中最大的连续子数组的和是多大？（|a[i]|<1e9， n<1e5）

输入
5
2 3 -10 4 4
输出
8

题解与代码

这题是经典的一题多解问题，常见的解法有动态规划和分治，都是经典例题级别的题目。此外，这题还可以使用前缀和来解决，思考思路为，对于第i个数结尾，只要前i个数的前缀和减去最小前缀和，就等价于以i结尾的最大后缀和，i从1到n遍历，答案一定在里面，因此该方法一定是正确的。时间复杂度O(n)

#include <iostream>
#include <vector>

using namespace std;

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

    vector<int> nums(n);
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }

    long long ans = -1e18;
    // 初始化当前前缀和为 0
    long long s1 = 0;
    // 初始化最小前缀和为 0
    long long s2 = 0;

    for (int x : nums) {
        // 计算当前位置的前缀和
        s1 += x;
        // 更新最大子数组和，即当前前缀和减去最小前缀和
        ans = max(ans, s1 - s2);
        // 更新最小前缀和
        s2 = min(s2, s1);
    }

    cout << ans << endl;

    return 0;
}

n = int(input())
nums = list(map(int, input().split()))
ans = float('-inf')

# 初始化当前前缀和为 0
s1 = 0
# 初始化最小前缀和为 0
s2 = 0
for x in nums:
    # 计算当前位置的前缀和
    s1 += x
    # 更新最大子数组和，即当前前缀和减去最小前缀和
    ans = max(ans, s1 - s2)
    # 更新最小前缀和
    s2 = min(s2, s1)

print(ans)

5.4 进阶-牛马国兵力侦查记（VIP）

https://oj.niumacode.com/problem/P1409

参考：https://leetcode.cn/problems/plates-between-candles/description/

牛马国有小牛和小马两员大将，某次多国混战中，各国的军队绞杀在一起，排成一排，用长度为n的字符串s表示，其中小牛手下的兵力使用字母'n'来表示，小马手下的兵力使用字母'm'来表示，其他国家的兵力用其他小写字母表示。现在有q个侦查兵，每个侦察兵使用望远镜只能观察到一个区间范围内的兵力情况，请问每个侦察兵分别可以观察到多少牛马国的兵力被左右夹击？即在观察范围内，有多少牛马国的兵力左侧和右侧都有敌国军队？（n,q<1e5）

输入
7 3
nmaanam
1 3
1 5
3 4
输出
2
3
0

思路与题解

前缀和，在前缀和维护前缀的基础上，多维护两个数组，分别代表i号军队左侧最近的敌军L和右侧最近的敌军R。维护复杂度同样也是O(n)，接着只需要对于每次查询l和r，输出R[l]到L[r]之间的牛马国军队即可，这也是前缀和预处理出来的，因此每次查询复杂度是O(n)。

ps：此外，这题也是可以二分的，感兴趣的同学可以自行在OJ上练习并提交二分解法。

#include <iostream>
#include <vector>
#include <string>

using namespace std;

const int MAXN = 100005;  
int sum[MAXN];
int L[MAXN];
int R[MAXN];
char s[MAXN];
int main() {
    int n, q;
    cin >> n >> q;
    cin >> s+1;

    vector<vector<int>> queries(q, vector<int>(2));
    for (int i = 0; i < q; ++i) {
        cin >> queries[i][0] >> queries[i][1];
    }

    for (int i = 1; i <= n; ++i) {
        sum[i] = sum[i-1] + (s[i] == 'n' || s[i]=='m');
    }

    // 计算每个位置左边最近的敌国军队
    L[0] = 0;
    for (int i = 1, l = -1; i <= n; ++i) {
        L[i] = L[i-1];
        if (!(s[i] == 'n' || s[i]=='m')) {
            L[i] = i;
        }
    }

    // 计算每个位置右边最近的敌国军队
    R[n+1] = n+1;
    for (int i = n, r = -1; i >= 1; --i) {
        R[i] = R[i+1];
        if (!(s[i] == 'n' || s[i]=='m')) {
            R[i] = i;
        }
    }

    vector<int> ans;
    for (auto& query : queries) {
        int l = R[query[0]], r = L[query[1]];
        if(l>=r) cout << 0 << endl;
        else cout << sum[r] - sum[l] << endl;
    }


    return 0;
}

5.5 进阶-K倍区间

https://oj.niumacode.com/problem/P1411

参考：蓝桥真题

给定一个长度为n的数组a，问有多少连续子数组，使得子数组的和是K的倍数？（1<=n,k<=1e5, 1<=a[i]<=1e5）

输入
3 2
1 2 3
输出
2

题解与代码

枚举第i个数结尾有多少个子数组是K的倍数，因此只需要看有多少个起点j，使得(sum[i]-sum[j])%k==0即可，转化为有多少j，使得sum[i]%k==sum[j]%k，因此用一个cnt数组一遍维护前缀和一遍维护计数，最终统计答案即可。时间复杂度O(n)，注意统计答案的时候需要先统计ans，后更新cnt数组，不然可能多统计上长度为0的非法答案了。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int a[N];
long long s[N], ans;
int n, k;
int cnt[N];
int main()
{
    cin>>n>>k;
    for (int i = 1; i<=n; i++) {
        cin>>a[i];
        s[i] = s[i-1] + a[i];
    }
    cnt[0] = 1;
    for (int i = 1; i<=n; i++) {
        ans += cnt[s[i]%k];
        cnt[s[i]%k] ++; //记录值为 s[i]%k 的s[i]的个数+1；
    }
    cout << ans << endl;
    return 0;
}

n, k = map(int, input().split())
a = [0] + list(map(int, input().split()))
s = [0] * (n + 1)

# 从1开始读入
for i in range(1, n + 1):
    s[i] = s[i - 1] + a[i]

ans = 0
# 初始化字典 cnt 用于记录每个余数出现的次数，初始余数 0 出现次数为 1
cnt = {0: 1}

for i in range(1, n + 1):
    t = s[i] % k
    ans += cnt.get(t, 0)
    cnt[t] = cnt.get(t, 0) + 1

print(ans)

5.6 进阶-小牛的科研时间段（VIP）

https://oj.niumacode.com/problem/P1161

小牛记录了自己每一天的科研时间表，上面详细记录了他每一天的科研小时数。当他一天中的科研时间超过 10 小时的时候，这一天就定义为「科研繁忙的一天」，反之则是「科研轻松的一天」。

定义「表现优异的时间段」是指在这段时间内，「科研繁忙的天数」是严格大于「科研轻松的天数」。

请你帮助小牛找出「表现优异的时间段」的最大长度。

输入
8
11 12 2 4 6 7 15 6
输出
3

思路与代码

本题解法多种多样，可以使用栈+贪心，也可以前缀和。这里主要讲一下使用前缀和的做法。由于本题主要关心a[i]与10的关系，因此可以先做1&-1变换，这样题意变为：找到一个最长的子数组，使得数组和>0。

维护前缀和sum，枚举到第i位的时候，维护以i为结尾的答案的情况，有两种情况：

1. 如果前缀和>0，则sum[i]一定就是答案。

1. 因为他一定最长，而且sum[i]还大于0，那太完美了。

2. 如果前缀和<=0，那就要找最早的sum[i]-1出现的位置，从该位置到i就是答案

1. 因为首先该位置一定是一个负数，因此在该位置再往前找，一定找不到更小的第一次出现的值了。

总时间复杂度O(n)。

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> hours(n);
    for (int i = 0; i < n; ++i) {
        cin >> hours[i];
    }

    map<int, int> mp;
    int s = 0, ans = 0;
    for (int i = 0; i < n; i++) {
        s += hours[i] > 10 ? 1 : -1;
        if (s > 0) {
            ans = max(ans, i + 1);
        } else {
            if (mp.count(s - 1)) {
                ans = max(ans, i - mp[s - 1]);
            }
        }
        if (!mp.count(s)) {
            mp[s] = i;
        }
    }
    cout << ans << endl;
    return 0;
}

5.7 进阶-最小和（VIP）

https://oj.niumacode.com/problem/P1412

参考：https://leetcode.cn/problems/minimum-positive-sum-subarray/description/

给定一个n个数的数组a，并且给定两个整数L和R，求满足下列条件的一个连续子数组的和。

1. 该连续子数组的和大于0。

2. 该连续子数组的长度在L到R之间。

3. 该连续子数组的和越小越好。

如果满足条件的连续子数组不存在，则输出-1.

（n<1e5, 1<=L<=R<=1e5, |a[i]| < 1e5）

输入
3 2 3
1 2 3
输出
2

题解与代码：

依旧是前缀和预处理，然后枚举右端点+维护左端点的信息。对于本题要求出子数组的和必须为正且和越小越好，对于枚举每一个i点当右端点，即找出i前面的一个j，使得sum[j]<sum[i]且越接近越好，且有子数组长度[l,r]内的要求，因此需要维护一个窗口大小为(r-l+1)的一个multiset，在里面用lower_bound找到我们要的j。同时随着右端点移动，r和l分别右移，O(logn)的维护时间。总时间复杂度O(nlogn)

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
long long a[100005], sum[100005];
multiset<int> ss;
int n, l, r;
int main() {
    
    cin >> n >> l >> r;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    long long ans = 1e17;

    for (int i = 1; i <= n; i++) {
        sum[i] = sum[i - 1] + a[i];
        if (i < l) {
            continue;
        }
        ss.insert(sum[i - l]);
        auto it = ss.lower_bound(sum[i]);
        if (it != ss.begin()) {
           --it;
            ans = min(ans, sum[i] - *it);
        }
        if (i >= r) {
            ss.erase(ss.find(sum[i - r]));
        }
    }
    if(ans == (long long)1e17) cout << -1 << endl;
    else cout << ans << endl;
    return 0;
}

六、常见陷阱

注意模板中是sum[l-1]，不要写错。

注意如果从0开始维护sum数组，则sum[0]需要单独处理防止越界，上文代码中默认从1开始维护数组。