C++基础算法前缀和和差分篇

这篇具有很好参考价值的文章主要介绍了C++基础算法前缀和和差分篇。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

📟作者主页:慢热的陕西人

🌴专栏链接:C++算法

📣欢迎各位大佬👍点赞🔥关注🚓收藏,🍉留言

主要讲解了前缀和和差分算法

C++基础算法前缀和和差分篇,算法,c++,开发语言

Ⅳ. 前缀和 和 差分

Ⅵ .Ⅰ前缀和

① 一维前缀和

​ 就是构建一个新的数组s,用来存储另一个数组的和前i个数组元素的和。用公式表达就是:
S [ i ] = a [ 0 ] + a [ 1 ] + . . . . a [ i ] S[i] = a[0]+a[1]+ .... a[i] S[i]=a[0]+a[1]+....a[i]
​ 这个结果我们用一次遍历就可以得到(我们的S只从1开始算起,为了方便后面的计算)

for(int i = 1; i < a.size(); ++i)
{
	s[i] = s[i - 1] + a[i];
}

具体的应用就是我们可以快速得到数组一个区间[l,r]内元素的和。
s [ l , r ] = s [ r ] = s [ l − 1 ] s[l, r] = s[r] = s[l - 1] s[l,r]=s[r]=s[l1]
对应题目:

B3645 数列前缀和 2 - 洛谷

②二维前缀和:

二维数组的前缀和就是相当于把一位数组的前缀和拓展成二维数组的前缀和。

那么我们计算s[i]的表达式为:
s [ i ] [ j ] = s [ i ] [ j − 1 ] + s [ i − 1 ] [ j ] − s [ i − 1 ] [ j − 1 ] + a [ i ] [ j ] s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + a[i][j] s[i][j]=s[i][j1]+s[i1][j]s[i1][j1]+a[i][j]
那么我们计算一个子矩阵[[i,l],[j,r]]的公式为
s [ [ i , l ] [ j , r ] ] = s [ l ] [ r ] − s [ i − 1 ] [ r ] − s [ l ] [ j − 1 ] + s [ i − 1 ] [ j − 1 ] s[[i,l][j,r]] = s[l][r] - s[i - 1][r] - s[l][j - 1] + s[i - 1][j - 1] s[[i,l][j,r]]=s[l][r]s[i1][r]s[l][j1]+s[i1][j1]
代码:

#include<iostream>
#include<stdlib.h>
using namespace std;

const int N = 1010;

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

int main()
{
    int n, m, q;
    int x1, x2, y1, y2;
    scanf("%d%d%d", &n, &m, & q);
    for(int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            scanf("%d", &a[i][j]);
    //计算前缀和
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];

    while (q--)
    {
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        printf("%d",(s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]));
    }
}

Ⅳ. Ⅱ 差分

① 一维差分

首先我们明确一个原则**差分是前缀和的逆运算,首先我们构建一个数组b和一个数组a,那么我们将b数组的前缀和存储在a数组中,我们这时候称b数组就是a数组的差分**a就是b的前缀和。

不难发现差分有这样一个性质:

a[l, r]加上一个常数c等价于b[l] += cb[r + 1] -= c.

这个性质非常的重要因为我们可以将a数组中的一些O(N)的操作降为b数组中O(1)的操作;

如下例题:

C++基础算法前缀和和差分篇,算法,c++,开发语言

代码:

#include<iostream>
#include<stdlib.h>
using namespace std;

const int N = 1000010;

int a[N], b[N];

void insert(int l, int r, int c)
{
    b[l] += c;
    b[r + 1] -= c;
}

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

    //利用性质算出差分
    for (int i = 1; i <= n; i++) insert(i, i, a[i]);

    
    while (m--)
    {
        int l, r, c;
        scanf("%d%d%d", &l, &r, &c);
        insert(l, r, c);
    }

    //通过b计算经过操作后产生的a
    for (int i = 1; i <= n; ++i) b[i] += b[i - 1];

    for (int i = 1; i <= n; ++i) printf("%d ", b[i]);
    return 0;
}

②二维差分(差分矩阵)

差分矩阵和上面的一维差分的思路差不多,首先我们构建一个矩阵b和一个矩阵a,那么我们将b矩阵的前缀和存储在a矩阵中,我们这时候称b矩阵就是a矩阵的差分a就是b的前缀和。

性质上也是类似的,但是略有不同:

a[[x1, x2],[y1,y2]]加上一个常数c等价于:
b [ x 1 , y 1 ] + = c b [ x 2 , y 1 ] − = c b [ x 1 , y 2 ] − = c b [ x 2 , y 2 ] + = c b[x1,y1] += c \\ b[x2, y1] -= c\\ b[x1, y2] -= c\\ b[x2, y2] += c b[x1,y1]+=cb[x2,y1]=cb[x1,y2]=cb[x2,y2]+=c
例题:

C++基础算法前缀和和差分篇,算法,c++,开发语言

代码:

#include<iostream>
#include<stdlib.h>
using namespace std;

const int N = 1010;

int a[N][N], b[N][N];

void insert(int x1, int y1, int x2, int y2, int c)
{
    b[x1][y1] += c;
    b[x2 + 1][y1] -= c;
    b[x1][y2  +1] -= c;
    b[x2 + 1][y2  +1] += c;
}

int main()
{
    int n, m, q;
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            scanf("%d", &a[i][j]);
    //利用性质构造差分
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            insert(i, j, i, j, a[i][j]);

    while (q--)
    {
        int x1, y1, x2, y2, c;
        scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);
        insert(x1, y1, x2, y2, c);
    }

    //计算前缀和矩阵
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];

    cout << endl;

    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
            printf("%d ", b[i][j]);
        cout << endl;
    }
    return 0;
}

到这本篇博客的内容就到此结束了。
如果觉得本篇博客内容对你有所帮助的话,可以点赞,收藏,顺便关注一下!
如果文章内容有错误,欢迎在评论区指正

C++基础算法前缀和和差分篇,算法,c++,开发语言文章来源地址https://www.toymoban.com/news/detail-596937.html

到了这里,关于C++基础算法前缀和和差分篇的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【有营养的算法笔记】基础算法 —— 推导证明前缀和与差分

    👑作者主页:@安 度 因 🏠学习社区:StackFrame 📖专栏链接:有营养的算法笔记 如果无聊的话,就来逛逛 我的博客栈 吧! 🌹 Hello,小伙伴们,好几天没有更新了,今天更了一篇比较“硬核的文章”。 主要内容为前缀和与差分算法的推导证明和代码实现。这篇文章博主还是画

    2024年01月21日
    浏览(46)
  • 算法基础学习笔记——④前缀和\差分\双指针\位运算

    ✨ 博主: 命运之光 ✨ 专栏: 算法基础学习 目录 ✨前缀和 ✨一维前缀和 🍓一维前缀和模板: ✨二维前缀和 🍓二位前缀和模板: 前言: 算法学习笔记记录日常分享,需要的看哈O(∩_∩)O,感谢大家的支持! 原i:a[1] a[2] a[3] …a[n] 前缀和:s[i]=a[1]+a[2]+…+a[i] s[0]=0(方便处理

    2024年02月08日
    浏览(46)
  • C++ 二维差分 二维前缀和逆运算 差分矩阵

    输入一个 n 行 m 列的整数矩阵,再输入 q 个操作,每个操作包含五个整数 x1,y1,x2,y2,c ,其中 (x1,y1) 和 (x2,y2) 表示一个子矩阵的左上角坐标和右下角坐标。 每个操作都要将选中的子矩阵中的每个元素的值加上 c 。 请你将进行完所有操作后的矩阵输出。 输入格式 第一行包含整数

    2024年02月21日
    浏览(52)
  • 前缀和&差分算法(Python版)

    前缀和与差分是常用的区间优化方式,其中前缀和数组可以将区间查询的时间复杂度降为常数,而差分数组则可以将区间修改的时间复杂度降为常数。 前缀和知识点简单易理解,但出题难度较大,需要根据题意挖掘出潜在的前缀和关系,建立辅助数组求解问题。 (1)一维前

    2024年04月17日
    浏览(52)
  • 【算法】—前缀和与差分详解

     前缀和指一个数组的某下标之前的所有数组元素的和( 即数列的前n项求和 ),前缀和是一种重要的 预处理 ,能够降低算法的时间复杂度,可以快速地求出某一段的和,对于处理区间之间的问题是往往十分高效 相比较其他算法而言, 前缀和更像是一种解题的技巧,一种优

    2024年02月04日
    浏览(52)
  • 洛谷题单--算法[2-1] 前缀和、差分与离散化

    目录 0.铺垫学习:p1115最大子段和--前缀和+贪心+DP 1.p1719最大加权矩形--前缀和+贪心+DP+矩阵压缩 原题链接: P1115 最大子段和 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 原题: 题目描述 给出一个长度为 n 的序列 a,选出其中连续且非空的一段使得这段和最大。 输入格式 第

    2024年02月22日
    浏览(37)
  • 一文带你深入了解算法笔记中的前缀与差分(附源码)

    📖作者介绍:22级树莓人(计算机专业),热爱编程<目前在c++阶段, 因为最近参加新星计划算法赛道(白佬),所以加快了脚步,果然急迫感会增加动力 ——目标Windows,MySQL,Qt,数据结构与算法,Linux,多线程,会持续分享学习成果和小项目的 📖作者主页:热爱编程的

    2023年04月12日
    浏览(60)
  • 二维前缀和&二维差分(超详细,python版,其他语言也很轻松能看懂)

    上一篇文章讲解了一维前缀和一维差分,本篇进阶为二维。 二维前缀和跟一维前缀和求法相同,这里直接上例子。 数组a = [[1,2,2,1],[3,2,2,1],[1,1,1,1]] a数组如图: 则数组a的前缀和为:数组b[[1,3,5,6],[4,8,12,14],[5,10,15,18]] b数组如图: 前缀和递推公式为 b[i][j] = b[i - 1][j] + b[i][j - 1]

    2024年04月22日
    浏览(38)
  • 高精度/前缀和/差分

    存储方式: 整数的长度一般小于1e6 大整数的每一位存储到数组里 存储时低位在前,高位在后,方便进位 高精度加法 每一位相加Ai + Bi + t, t表示进位取值0/1,逢十进一 模板: 高精度减法 每一位相减Ai - Bi - t, t 表示借位取值0/1 模板: 高精度乘法 A * b ,b=10000, len(A) = 1e6 , 乘的

    2024年02月16日
    浏览(48)
  • 前缀和&差分

    前缀和:一段序列里的前n项和 给出n个数,在给出q次问询,每次问询给出L、R,快速求出每组数组中一段L至R区间的和 给出一段数组,每次问询为求出l到r区间的和 普通方法: L到R进行遍历,那么在每次求区间和的过程中时间复杂度为O(n),q次问询时间复杂度为O(q*n) 前缀和:

    2024年02月15日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包