【算法合集】前缀和与差分

简介: 字面意思前面数到后面数的和(又叫区间和),假设我们有一组数组[1,2,3,4,5],输入左区间与右区间,这区间它们两的和(不是下标哟)。

一、前缀和

1、一维前缀和

啥是前缀和?

字面意思前面数到后面数的和(又叫区间和),假设我们有一组数组[1,2,3,4,5],输入左区间与右区间,这区间它们两的和(不是下标哟)。

例子

数组长度为 6 ,元素是[1,2,3,4,5,6],区间 1 到 3 的和是6,这样的就叫一维前缀和。

直接看代码

#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 10;
int n, m;
int arr[N], srr[N];
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> arr[i];
    for (int i = 1; i <= n; i ++ ) srr[i] = srr[i - 1] + arr[i];
    while (m -- )
    {
        int l, r;
        cin >> l >> r;
        cout << srr[r] - srr[l - 1] << endl;
    }
    return 0;
}

image.gif

image.png

n 是数组的长度,m 是要操作的次数,l 是左区间,r是右区间

2、二维前缀和

image.png

啥是二维前缀和?

我们直接看图

假设 a 是个大区间的我们要求 d 区间的数据和,先求 f 的和再减去两个 b 区间的和,b 区间明显多减了一次,所以左后面再加上 c 区间。

image.png

假设有一个长度为 5 宽度为 3 的一个数组,里面都是1,2,3数据,坐标(1,1)到(2,2)的和明显是 1 + 2 + 1 + 2。

#include <bits/stdc++.h>
using namespace std;
const int N = 1000 + 10;
int n, m, q;
int arr[N][N], srr[N][N];
int main()
{
    cin >> n >> m >> q;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            cin >> arr[i][j];
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            srr[i][j] = arr[i][j] + srr[i - 1][j] + srr[i][j - 1] - srr[i - 1][j - 1];
    while (q --)
    {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << srr[x2][y2] - srr[x2][y1 - 1] - srr[x1 - 1][y2] + srr[x1 - 1][y1 - 1] << endl;
    }
    return 0;
}

image.gif

二、差分

1、一维差分

通过上面我们知道了,什么是前缀和,那么什么是差分呢?就是在一区间减去某一个数或加上某一个数,假如 1 到 3 区间有1,2,3 三个数据,对它进行 + 1 与 - 2操作,再来求它的和,这就是典型的差分。

image.png

#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 10;
int n, m, arr[N], srr[N];
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
    {
        cin >> arr[i];
        srr[i] += arr[i];
        srr[i + 1] -= arr[i];
    }
    while(m --)
    {
        int l, r, c;
        cin >> l >> r >> c;
        srr[l] += c;
        srr[r + 1] -= c;
    }
    for(int i = 1; i <= n; i ++)
    {
        srr[i] += srr[i - 1];
        cout << srr[i] << ' ';
    }
}

image.gif

2、二维差分

同样的道理这里就不多说了。

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, m, q;
int arr[N][N], srr[N][N];
int main()
{
    cin >> n >> m >> q;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            scanf("%d", &srr[i][j]);
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            arr[i][j] = srr[i][j] - srr[i - 1][j] - srr[i][j - 1] + srr[i - 1][j - 1];
    while (q --)
    {
        int x1, y1, x2, y2, c;
        scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);
        arr[x1][y1] += c;
        arr[x1][y2 + 1] -= c;
        arr[x2 + 1][y1] -= c;
        arr[x2 + 1][y2 + 1] += c;
    }
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            srr[i][j] = arr[i][j] + srr[i - 1][j] + srr[i][j - 1] - srr[i - 1][j - 1];
    for (int i = 1; i <= n; i ++ )
    {
        for (int j = 1; j <= m; j ++ ) printf("%d ", srr[i][j]);
        cout << endl;
    }
    return 0;
}


相关文章
|
5天前
|
机器学习/深度学习 边缘计算 分布式计算
基于差分进化算法的微电网调度研究(Matlab代码实现)
基于差分进化算法的微电网调度研究(Matlab代码实现)
|
3月前
|
机器学习/深度学习 算法
基于差分进化灰狼混合优化的SVM(DE-GWO-SVM)数据预测算法matlab仿真
本项目实现基于差分进化灰狼混合优化的SVM(DE-GWO-SVM)数据预测算法的MATLAB仿真,对比SVM和GWO-SVM性能。算法结合差分进化(DE)与灰狼优化(GWO),优化SVM参数以提升复杂高维数据预测能力。核心流程包括DE生成新种群、GWO更新位置,迭代直至满足终止条件,选出最优参数组合。适用于分类、回归等任务,显著提高模型效率与准确性,运行环境为MATLAB 2022A。
|
6月前
|
机器学习/深度学习 算法 机器人
强化学习:时间差分(TD)(SARSA算法和Q-Learning算法)(看不懂算我输专栏)——手把手教你入门强化学习(六)
本文介绍了时间差分法(TD)中的两种经典算法:SARSA和Q-Learning。二者均为无模型强化学习方法,通过与环境交互估算动作价值函数。SARSA是On-Policy算法,采用ε-greedy策略进行动作选择和评估;而Q-Learning为Off-Policy算法,评估时选取下一状态中估值最大的动作。相比动态规划和蒙特卡洛方法,TD算法结合了自举更新与样本更新的优势,实现边行动边学习。文章通过生动的例子解释了两者的差异,并提供了伪代码帮助理解。
418 2
|
算法
【算法】前缀和——二维前缀和模板题
【算法】前缀和——二维前缀和模板题
109 0
|
算法
【算法】前缀和——前缀和
【算法】前缀和——前缀和
106 0
|
9月前
|
算法
|
12月前
|
存储 算法 Java
前缀和算法
本文介绍了前缀和及其变种在解决区间求和问题中的应用。首先,一维前缀和可通过预处理数组快速求得任意区间的和。接着,二维前缀和扩展了这一思想,适用于矩阵操作。此外,文章探讨了如何利用前缀和解决诸如“寻找数组中心下标”、“除自身以外数组的乘积”等问题,并进一步讲解了涉及哈希表优化的“和为 K 的子数组”等相关题目。最后,通过实例展示了如何在矩阵中高效计算特定区域的元素之和。文中包含代码示例与图解说明,便于理解。
112 0
前缀和算法
|
人工智能 算法 JavaScript
【算法】前缀和与差分
算法学习——前缀和与差分(含一维和二维)
149 4
【算法】前缀和与差分
|
11月前
|
人工智能 算法 BI
一篇带你速通差分算法(C/C++)
一篇带你速通差分算法(C/C++)
|
11月前
|
人工智能 算法 C++
一篇带你速通前缀和算法(C/C++)
一篇带你速通前缀和算法(C/C++)

热门文章

最新文章