C++U4-第10课-前缀和与差分-526互联

学习目标

前缀和解决的问题

前缀和概念

前缀和构建方式

前缀和主要解决区间求和问题

练习题1：[前缀和]

【算法分析】
前缀和数组 s 的含义是 s[i] 表示 a[1] ~ a[i] 的和 ，那么 ∑ 
i=l
i=r

 a[i] = s[r]−s[l−1]。

【参考代码】
#include <iostream>
using namespace std;

int a[100010], s[100010];

int main() {
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        s[i] = s[i - 1] + a[i]; 
    }
    int l, r;
    while(m--){
        cin >> l >> r;
        cout << s[r] - s[l - 1] << endl;
    }
    return 0;
}

View Code

练习题2：[7的倍数的子序列]

/*
流程解析：
输入数组的长度n。
循环读入n个数组元素，存储在数组a中。
根据题目要求，计算前缀和并对7取模，保存在pre数组中。
初始化左边界l为-1，右边界r为0。
遍历pre数组，更新左边界l和右边界r，确保每个模值pre[i]的最小左边界和最大右边界被记录下来。
遍历0到6之间的所有模值，计算相应模值的子数组长度，保存在ans中。
输出ans作为结果。
这段代码的目标是找到一个子数组，使得该子数组中所有元素相加后对7取模的结果最大。最后输出最大结果ans。


提示1：对结果取余 和对过程取余   是一样的 
累加和整体取余：4+5+6+7+8=30     30%4   余2 
逐个取余再加在一起再取余：逐个取余   0  1  2  3  0   6%4   = 2
*/

#include <iostream>
using namespace std;
int a[50010], pre[50010];
int r[7];  //记录最后出现的位置          
int l[7] = {0, -1 ,-1,-1 ,-1,-1,-1}; // 初始化，记录每个余数最早出现的位置              
int main() {
    int n, ans; // 输入变量和答案变量
    cin >> n; // 输入数组长度
    for(int i = 1; i <= n; i++){
        cin >> a[i]; // 输入数组元素
        pre[i] = (pre[i - 1] + a[i]) % 7; // 计算前缀和%7的结果
        if(l[pre[i]] == -1) l[pre[i]] = i; // 更新左边界
        r[pre[i]] = i; // 更新右边界
    }
    for(int i = 0; i <= 6; i++){
        ans = max(ans, r[i] - l[i]); // 计算最长子数组的长度
    }
    cout << ans; // 输出结果
    return 0;
}

差分数组

差分数组解决的问题

差分构建方式

差分数组解决的使用方式

范围内的数字进行改变的方式

练习题

【算法分析】
差分的定义：
差分指的是在序列中相邻两项之间的差值。
对于一个序列 (a1,a2,a3,⋯)，它的差分序列是一个新的数列 (d1,d2,d3,⋯)，其中 di=a 
i+1−ai。也就是说，差分序列中的每一项都是原序列中相邻两项之差。
在进行操作时，[l,r] 之间的数都加上 c，可以在对应的差分序列中做以下操作：
b[l] += c;
b[r+1] -= c;
操作完成，对差分数组求前缀和即可得到结果。

【参考代码】
#include <iostream>
using namespace std;

const int N = 100010;
int a[N], b[N];

int main(){
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    for(int i = 1; i <= n; i++){ //差分数组
        b[i] = a[i] - a[i - 1];
    }
    while(m--){                 //m次操作
        int l, r, c;
        cin >> l >> r >> c;
        b[l] += c;
        b[r + 1] -= c;
    }
    for(int i = 1; i <= n; i++){ //前缀和
        b[i] += b[i - 1];
        cout << b[i] << " ";
    }
    return 0;
}

View Code

练习2

【算法分析】
这道题只要计算 a[i] 和 a[i+1] 两组的高度差即可：

a[i]<a[i+1]，即左边的一组比右边的矮，当高度满足左边时，右边的还差一些，那么 ans 加上两堆的高度差；

a[i]>=a[i+1]，即左边的一组比右边的高，当高度满足左边时，右边的也一定满足了，所以不需要增加 ans。

【参考代码】
#include <iostream>
using namespace std;

const int N = 100010;
int a[N], b[N];
long long ans;

int main(){
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    for(int i = 1; i <= n; i++){
        b[i] = a[i] - a[i - 1];
        if(b[i] > 0) ans += b[i];
    }
    cout << ans;
    return 0;
}

View Code

本节课作业讲解：

链接：https://pan.baidu.com/s/1CRedzyqQEEvF39S2bZHFCA?pwd=n5dl
提取码：n5dl