前缀和专题练习 ——基于罗勇军老师的《蓝桥杯算法入门C/C++》

一、0求和 - 蓝桥云课

算法代码：

代码思路概述

代码详细解释

数组定义

输入读取

前缀和计算部分

结果计算部分

输出结果

程序结束

总结

二、1.可获得的最小取值 - 蓝桥云课

算法代码：

代码思路概述

详细代码逻辑解释

输入初始化

读取数组元素

数组排序

前缀和计算

求最小值

输出结果

总结

三、P1811 - [NewOJ Week 5] 并行处理 - New Online Judge

算法代码：

代码思路

输入数组

计算前缀和

寻找最优分割点

输出结果

代码分析

时间复杂度

空间复杂度

适用场景

示例

总结

四、1.异或和之和 - 蓝桥云课

算法代码：

代码思路

输入数组

逐位计算贡献

累加结果

输出结果

代码分析

时间复杂度

空间复杂度

适用场景

示例

总结

1. 问题背景

什么是子数组？

什么是异或和？

2. 核心思想

3. 具体实现

前缀异或和

动态维护计数

为什么需要 zero 和 one？

4. 代码逻辑详解

外层循环：逐位计算贡献

初始化

内层循环：遍历数组

获取当前二进制位的值

更新前缀异或和

统计贡献

累加当前位的贡献

5. 示例

6. 总结

五、P2004 领地选择 - 洛谷

算法代码：

代码思路

输入矩阵和参数

计算前缀和矩阵

寻找最大子矩阵

输出结果

代码分析

时间复杂度

空间复杂度

适用场景

示例

总结

一、0求和 - 蓝桥云课

算法代码：

#include<stdio.h>int a[200010];          // 定义一个整数数组 a，最大长度为 200010
long long sum[200010]; // 定义一个长整型数组 sum，用于存储前缀和int main() {int n;             // 定义变量 n，表示数组的长度scanf("%d", &n);  // 从标准输入读取数组的长度 n// 读取数组元素并计算前缀和for(int i=1; i<=n; i++) {scanf("%d", &a[i]);            // 读取数组 a 的第 i 个元素sum[i] = sum[i-1] + a[i];      // 计算前缀和：sum[i] 为前 i 个元素的和}long long s = 0; // 初始化结果变量 s 为 0，注意局部变量在使用前需初始化// 计算特定值 sfor(int i=1; i<=n; i++) {// s 加上 a[i] 乘以 sum[n]（全数组和）减去 sum[i]（前 i 个元素的和）s += a[i] * (sum[n] - sum[i]); // sum[n] - sum[i] 为 a[i] 后面所有元素的和}printf("%lld\n", s); // 输出计算的结果 s，格式为长整型return 0; // 程序正常结束
}

代码思路概述

输入处理: 读取整数数组的长度和数据。
前缀和计算: 使用前缀和数组存储从数组头到当前位置的累积和，以便后续快速计算。
结果计算: 根据前缀和数组计算特定的结果。
输出结果: 将计算的结果输出。

代码详细解释

数组定义
- int a[200010];：声明一个整数数组 a，用于存储数组的元素。
- long long sum[200010];：声明一个长整型数组 sum，用于存储前缀和，以便处理大数。
输入读取
- scanf("%d", &n);：读取用户输入的数组长度 n。
前缀和计算部分
- for(int i=1; i<=n; i++)：循环从 1 到 n，读取数组元素并计算前缀和。
  - scanf("%d", &a[i]);：读取第 i 个元素并存储在数组 a 中。
  - sum[i] = sum[i-1] + a[i];：更新前缀和数组 sum，其中 sum[i] 表示从 a[1] 到 a[i] 的总和。
结果计算部分
- long long s = 0;：初始化结果变量 s 为 0。
- for(int i=1; i<=n; i++)：循环从 1 到 n，计算每个元素对最终结果的贡献。
  - s += a[i] * (sum[n] - sum[i]);：将当前元素 a[i] 乘以其后所有元素的和（通过前缀和计算），并累加到 s 中。sum[n] 是整个数组的和，sum[i] 是前 i 个元素的和，所以 sum[n] - sum[i] 是从 a[i+1] 到 a[n] 的和。
输出结果
- printf("%lld\n", s);：输出结果 s，注意格式为长整型。
程序结束
- return 0;：返回 0，表示程序正常结束。

总结

这段代码实现了通过前缀和的方式高效地计算数组中元素的特定总和，避免了重复计算，提升了效率。每一步都通过清晰的逻辑和注释展现了代码的目的和功能。

下面的代码思路是差不多的：

#include <iostream>
using namespace std;
typedef long long ll;
int a[200005];
int main()
{// 请在此输入您的代码int n;ll sum=0,ans=0;scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d",&a[i]);sum+=a[i];}for(int i=0;i<n;i++){sum-=a[i];ans+=a[i]*sum;}printf("%lld",ans);return 0;
}

二、1.可获得的最小取值 - 蓝桥云课

算法代码：

#include <bits/stdc++.h>
using namespace std;long long a[200010]; // 定义一个长整型数组 a，用于存储输入的数字
long long sum[200010]; // 定义一个长整型数组 sum，用于存储前缀和int main() {int n, k; // 定义变量 n（数组长度）和 k（操作参数）cin >> n >> k; // 从标准输入读取 n 和 k 的值// 读取数组元素for (int i = 1; i <= n; i++) {cin >> a[i]; // 读取第 i 个元素到数组 a 中}// 对数组进行排序sort(a + 1, a + 1 + n); // 从 a[1] 到 a[n] 排序// 计算前缀和for (int i = 1; i <= n; i++) {sum[i] = sum[i - 1] + a[i]; // sum[i] 存储从 a[1] 到 a[i] 的总和}long long ans = 1e18; // 初始化结果变量 ans 为一个很大的值，代表正无穷大// 计算最小值for (int p = 1; p <= k; p++) {// 计算一个特定的值并更新 ansans = min(sum[n] - sum[n + p - k] + sum[2 * p], ans);}cout << ans; // 输出结果 ansreturn 0; // 程序正常结束
}

代码思路概述

输入处理: 读取数组的长度 n 和参数 k，并填充数组。
排序: 对数组进行升序排序，以便后续计算。
前缀和计算: 计算前缀和，这样可以快速获得数组中任意区间的和。
计算特定值: 根据给定的条件和公式计算最小值。
输出结果: 将计算得到的最小值输出。

详细代码逻辑解释

输入初始化
- 定义长整型数组 a 和 sum，用于存储输入的数据和计算的前缀和。
- 读取用户输入的两个整数 n（数组长度）和 k（控制参数）。
读取数组元素
- 使用循环读取 n 个元素到数组 a 中。注意，数组从 1 开始填充，这在一些 C++ 代码中是为了方便后续计算（通常使用 1 为数组索引）。
数组排序
- 使用 sort 函数对数组 a 进行升序排序，以便在后续的计算中能够利用排序后的结构。
前缀和计算
- 使用一个循环计算前缀和，sum[i] 存储从 a[1] 到 a[i] 的总和。这样可以方便地在 O(1) 时间内计算任意区间的和。
求最小值
- 初始化结果 ans 为一个非常大的值（例如 1e18），以确保后续的比较能够更新这个值。
- 使用循环，遍历 p 从 1 到 k，根据给定的公式计算每个 p 对应的值，并更新最小值 ans。
- sum[n] - sum[n + p - k] + sum[2 * p] 公式的具体含义可能与问题的特定定义有关，通常用于计算某种区间和的差异或者总和。
输出结果
- 最终，将计算得到的最小值 ans 输出。

总结

全局视角: 该代码实现了一个高效的算法，通过排序和前缀和来简化后续的计算。
时间复杂度: 整个过程的时间复杂度主要由排序决定，即 O(n log n)，而前缀和计算和最小值查找都是 O(n) 的，因此整体复杂度是 O(n log n)。
空间复杂度: 使用了 O(n) 的额外空间来存储输入数组和前缀和数组。
适用场景: 此类算法适用于需要频繁计算区间和或求最值的问题，在处理大规模数据时尤其有效。

三、P1811 - [NewOJ Week 5] 并行处理 - New Online Judge

算法代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
long long sum[N];
int main()
{int n;cin >> n;for (int i = 1; i <= n; i++){int a;cin >> a;sum[i] = sum[i - 1] + a;}long long ans = sum[n];for (int i = 1; i <= n; i++){ans = min(ans, max(sum[i], sum[n] - sum[i]));}cout << ans << endl;return 0;
}

代码思路

输入数组
- 首先输入一个整数 n，表示数组的长度。
- 然后输入 n 个整数，表示数组的元素。
计算前缀和
- 使用一个数组 sum 来存储前缀和，其中 sum[i] 表示数组前 i 个元素的和。
- 前缀和的计算公式为：sum[i] = sum[i - 1] + a，其中 a 是当前输入的元素。
寻找最优分割点
- 初始化 ans 为整个数组的和 sum[n]。
- 遍历数组，尝试将数组分成两部分：前 i 个元素和后 n - i 个元素。
- 对于每个分割点 i，计算两部分的和：sum[i] 和 sum[n] - sum[i]。
- 取这两部分的最大值，并更新 ans 为所有最大值中的最小值。
输出结果
- 输出 ans，即最优分割点对应的最大值的最小值。

代码分析

时间复杂度
- 计算前缀和的时间复杂度为 O(n)O(n)。
- 寻找最优分割点的时间复杂度为 O(n)O(n)。
- 总时间复杂度为 O(n)O(n)。
空间复杂度
- 使用了一个大小为 NN 的数组 sum 来存储前缀和，空间复杂度为 O(n)O(n)。
适用场景
- 这段代码适用于需要将数组分成两部分，并使得两部分的最大值最小化的问题。
- 例如，在任务分配问题中，可能需要将任务分成两组，使得两组的总工作量尽可能均衡。

示例

假设输入如下：

5
1 2 3 4 5

前缀和数组 sum 为：[0, 1, 3, 6, 10, 15]。
遍历分割点：
- i = 1：max(1, 14) = 14
- i = 2：max(3, 12) = 12
- i = 3：max(6, 9) = 9
- i = 4：max(10, 5) = 10
- i = 5：max(15, 0) = 15
最小值为 9，因此输出 9。

总结

这段代码的核心思想是通过前缀和快速计算任意子数组的和，然后遍历所有可能的分割点，找到使得两部分最大值最小化的最优解。代码实现简洁高效，适用于类似的问题场景。

四、1.异或和之和 - 蓝桥云课

算法代码：

#include <bits/stdc++.h>
using namespace std;int main()
{int n;cin >> n;vector<int> a(n);for (int i = 0; i < n; i++){cin >> a[i]; // 输入数组}long long ans = 0; // 初始化结果为 0for (int k = 0; k <= 20; k++) // 遍历每个二进制位{int zero = 1, one = 0; // 初始化前缀异或和为 0 和 1 的次数long long cnt = 0, sum = 0; // cnt 记录当前位的贡献，sum 记录前缀异或和for (int i = 0; i < n; i++) // 遍历数组{int v = (a[i] >> k) & 1; // 获取当前元素在第 k 位的值sum ^= v; // 更新前缀异或和if (sum == 0) // 如果前缀异或和为 0{zero++; // 增加 zero 的计数cnt += one; // 累加 one 的贡献}else // 如果前缀异或和为 1{one++; // 增加 one 的计数cnt += zero; // 累加 zero 的贡献}}ans += cnt * (1ll << k); // 将当前位的贡献累加到结果中}cout << ans; // 输出结果return 0;
}

代码思路

输入数组
- 首先输入一个整数 n，表示数组的长度。
- 然后输入 n 个整数，表示数组的元素。
逐位计算贡献
- 对于每个二进制位 k（从 0 到 20），计算该位对最终结果的贡献。
- 使用变量 sum 来记录当前前缀异或和。
- 使用变量 zero 和 one 来记录前缀异或和为 0 和 1 的次数。
- 遍历数组，计算每个元素在当前二进制位上的值 v = (a[i] >> k) & 1，并更新前缀异或和 sum。
- 根据 sum 的值，更新 zero 和 one 的计数，并累加当前位的贡献 cnt。
累加结果
- 将每个二进制位的贡献 cnt 乘以 (1 << k)，并累加到最终结果 ans 中。
输出结果
- 输出 ans，即所有子数组异或和的总和。

代码分析

时间复杂度
- 外层循环遍历每个二进制位，最多 21 次（0 到 20）。
- 内层循环遍历数组，时间复杂度为 O(n)O(n)。
- 总时间复杂度为 O(21×n)O(21×n)，即 O(n)O(n)。
空间复杂度
- 使用了一个大小为 nn 的数组 a，空间复杂度为 O(n)O(n)。
适用场景
- 这段代码适用于需要计算所有子数组异或和总和的问题。
- 例如，在统计数组中所有子数组的异或和时，可以通过逐位计算贡献来高效求解。

示例

假设输入如下：

3
1 2 3

对于每个二进制位 k，计算贡献：
- k = 0：
  - 子数组异或和在第 0 位的贡献为 4。
- k = 1：
  - 子数组异或和在第 1 位的贡献为 4。
- k = 2：
  - 子数组异或和在第 2 位的贡献为 0。
最终结果为 4×1+4×2+0×4=124×1+4×2+0×4=12。

总结

这段代码的核心思想是通过逐位计算每个二进制位对最终结果的贡献，从而高效地求解所有子数组异或和的总和。代码实现简洁高效，适用于类似的问题场景。

1. 问题背景

这段代码的目的是计算数组中所有子数组的异或和的总和。异或和是指一个子数组中所有元素的异或结果。我们需要对数组中所有可能的子数组计算异或和，然后将这些异或和相加，得到最终的结果。

什么是子数组？

子数组是数组中连续的一段元素。例如，数组 [1, 2, 3] 的子数组包括：

[1]
[2]
[3]
[1, 2]
[2, 3]
[1, 2, 3]

什么是异或和？

异或和是指一个子数组中所有元素的异或结果。例如：

子数组 [1, 2] 的异或和是 1 ^ 2 = 3。
子数组 [2, 3] 的异或和是 2 ^ 3 = 1。

2. 核心思想

为了高效计算所有子数组的异或和的总和，代码采用了逐位计算贡献的方法。具体来说：

对于每个二进制位（从第 0 位到第 20 位），计算该位对最终结果的贡献。
如果某个子数组的异或和在第 kk 位上是 1，那么该子数组对最终结果的贡献是 1×(1≪k)1×(1≪k)。
我们需要统计有多少子数组的异或和在第 kk 位上是 1，然后将这些贡献累加起来。

3. 具体实现

为了实现上述思想，代码使用了前缀异或和和动态维护计数的方法。

前缀异或和

前缀异或和 sum 表示从数组开头到当前位置的子数组的异或和。
例如，对于数组 [1, 2, 3]：
- 到第 1 个元素的前缀异或和是 1。
- 到第 2 个元素的前缀异或和是 1 ^ 2 = 3。
- 到第 3 个元素的前缀异或和是 1 ^ 2 ^ 3 = 0。

动态维护计数

我们需要统计有多少子数组的异或和在第 kk 位上是 1。
为了实现这一点，代码维护了两个变量：
- zero：表示前缀异或和为 0 的次数。
- one：表示前缀异或和为 1 的次数。

为什么需要 `zero` 和 `one`？

假设我们有两个位置 ii 和 jj（i<ji<j），如果前缀异或和在位置 ii 和位置 jj 的值相同（都是 0 或都是 1），那么从 i+1i+1 到 jj 的子数组的异或和为 0。
如果前缀异或和在位置 ii 和位置 jj 的值不同（一个是 0，另一个是 1），那么从 i+1i+1 到 jj 的子数组的异或和为 1。

因此，通过维护 zero 和 one 的计数，我们可以快速计算有多少子数组的异或和为 1。

4. 代码逻辑详解

以下是代码的核心逻辑，逐行解释：

外层循环：逐位计算贡献

for (int k = 0; k <= 20; k++)

遍历每个二进制位（从第 0 位到第 20 位）。
对于每个二进制位，计算该位对最终结果的贡献。

初始化

int zero = 1, one = 0;
long long cnt = 0, sum = 0;

zero：初始化为 1，表示前缀异或和为 0 的次数（初始状态的前缀异或和为 0）。
one：初始化为 0，表示前缀异或和为 1 的次数。
cnt：记录当前二进制位的贡献。
sum：记录当前的前缀异或和。

内层循环：遍历数组

for (int i = 0; i < n; i++)

遍历数组中的每个元素。

获取当前二进制位的值

int v = (a[i] >> k) & 1;

获取当前元素在第 kk 位上的值（0 或 1）。

更新前缀异或和

sum ^= v;

更新前缀异或和 sum。

统计贡献

if (sum == 0)
{zero++;cnt += one;
}
else
{one++;cnt += zero;
}

如果 sum == 0：
- 当前前缀异或和为 0。
- 如果之前存在某个前缀异或和为 1 的位置，那么从那个位置到当前位置的子数组的异或和为 1。
- 因此，累加 one 的贡献到 cnt 中。
- 同时，zero 的计数加 1，因为当前前缀异或和为 0。
如果 sum == 1：
- 当前前缀异或和为 1。
- 如果之前存在某个前缀异或和为 0 的位置，那么从那个位置到当前位置的子数组的异或和为 1。
- 因此，累加 zero 的贡献到 cnt 中。
- 同时，one 的计数加 1，因为当前前缀异或和为 1。

累加当前位的贡献

ans += cnt * (1ll << k);

将当前二进制位的贡献 cnt 乘以 1≪k1≪k，并累加到最终结果 ans 中。

5. 示例

假设数组为 [1, 2, 3]，我们以第 0 位（最低位）为例：

二进制表示：
- 1 的第 0 位是 1。
- 2 的第 0 位是 0。
- 3 的第 0 位是 1。
计算过程：
- 初始化：zero = 1，one = 0，sum = 0，cnt = 0。
- 遍历数组：
  1. 第 1 个元素 1：
    - v = (1 >> 0) & 1 = 1。
    - sum = sum ^ v = 0 ^ 1 = 1。
    - 因为 sum == 1，所以累加 zero 的贡献：cnt += zero = 1。
    - 更新 one：one = 1。
  2. 第 2 个元素 2：
    - v = (2 >> 0) & 1 = 0。
    - sum = sum ^ v = 1 ^ 0 = 1。
    - 因为 sum == 1，所以累加 zero 的贡献：cnt += zero = 2。
    - 更新 one：one = 2。
  3. 第 3 个元素 3：
    - v = (3 >> 0) & 1 = 1。
    - sum = sum ^ v = 1 ^ 1 = 0。
    - 因为 sum == 0，所以累加 one 的贡献：cnt += one = 4。
    - 更新 zero：zero = 2。
最终，第 0 位的贡献为 cnt = 4。

6. 总结

if 和 else 中增加 one 或 zero 的贡献，是为了统计当前二进制位上有多少子数组的异或和为 1。
通过维护 zero 和 one 的计数，可以快速计算这些子数组的数量，从而高效地计算每个二进制位对最终结果的贡献。
这种方法的本质是利用前缀异或和的性质，将问题转化为统计满足条件的子数组数量。

五、P2004 领地选择 - 洛谷

算法代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
int a[N][N], s[N][N];int main()
{int n, m, c;cin >> n >> m >> c; // 输入矩阵的行数、列数和子矩阵的大小// 输入矩阵并计算前缀和矩阵for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++){cin >> a[i][j]; // 输入矩阵元素s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j]; // 计算前缀和}int Max = -1 << 30, x, y; // 初始化最大值和坐标// 遍历所有可能的子矩阵for (int x1 = 1; x1 <= n - c + 1; x1++)for (int y1 = 1; y1 <= m - c + 1; y1++){int x2 = x1 + c - 1, y2 = y1 + c - 1; // 计算右下角坐标// 计算子矩阵的元素和int ans = s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1];if (ans > Max) // 如果当前子矩阵的元素和更大{Max = ans; // 更新最大值x = x1, y = y1; // 更新左上角坐标}}cout << x << " " << y << endl; // 输出结果return 0;
}

代码思路

输入矩阵和参数
- 输入三个整数 n、m 和 c，分别表示矩阵的行数、列数以及子矩阵的大小。
- 输入一个 n×mn×m 的矩阵 a，表示矩阵的元素。
计算前缀和矩阵
- 使用一个二维数组 s 来存储前缀和矩阵，其中 s[i][j] 表示从 (1, 1) 到 (i, j) 的子矩阵的元素和。
- 前缀和的计算公式为：
  s[i][j]=s[i−1][j]+s[i][j−1]−s[i−1][j−1]+a[i][j]s[i][j]=s[i−1][j]+s[i][j−1]−s[i−1][j−1]+a[i][j]
寻找最大子矩阵
- 遍历所有可能的 c×cc×c 子矩阵的左上角坐标 (x1, y1)。
- 对于每个左上角坐标 (x1, y1)，计算对应的右下角坐标 (x2, y2)，其中 x2 = x1 + c - 1，y2 = y1 + c - 1。
- 使用前缀和矩阵快速计算子矩阵的元素和：
  ans=s[x2][y2]−s[x2][y1−1]−s[x1−1][y2]+s[x1−1][y1−1]ans=s[x2][y2]−s[x2][y1−1]−s[x1−1][y2]+s[x1−1][y1−1]
- 如果当前子矩阵的元素和 ans 大于之前的最大值 Max，则更新 Max 和对应的左上角坐标 (x, y)。
输出结果
- 输出最大子矩阵的左上角坐标 (x, y)。

代码分析

时间复杂度
- 计算前缀和矩阵的时间复杂度为 O(n×m)O(n×m)。
- 遍历所有可能的子矩阵的时间复杂度为 O((n−c+1)×(m−c+1))O((n−c+1)×(m−c+1))。
- 总时间复杂度为 O(n×m)O(n×m)。
空间复杂度
- 使用了两个大小为 N×NN×N 的二维数组 a 和 s，空间复杂度为 O(n×m)O(n×m)。
适用场景
- 这段代码适用于需要在二维矩阵中快速查找某个固定大小的子矩阵，并计算其元素和的问题。
- 例如，在图像处理中，可能需要查找某个区域的最大亮度值。

示例

假设输入如下：

4 4 2
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

前缀和矩阵 s 为：

1   3   6  10
6  14  24  36
15 33  54  78
28 60  96 136

遍历所有 2×22×2 的子矩阵：
- 左上角 (1, 1)，元素和为 14。
- 左上角 (1, 2)，元素和为 18。
- 左上角 (1, 3)，元素和为 22。
- 左上角 (2, 1)，元素和为 30。
- 左上角 (2, 2)，元素和为 34。
- 左上角 (2, 3)，元素和为 38。
- 左上角 (3, 1)，元素和为 46。
- 左上角 (3, 2)，元素和为 50。
- 左上角 (3, 3)，元素和为 54。
最大子矩阵的左上角坐标为 (3, 3)，元素和为 54。

总结

这段代码的核心思想是通过前缀和矩阵快速计算任意子矩阵的元素和，然后遍历所有可能的子矩阵，找到元素和最大的子矩阵。代码实现简洁高效，适用于类似的问题场景。