前缀和、差分

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

前缀和、差分

前缀和可以快速求区间和。
差分相当于前缀和的逆运算。
前缀和、差分都是以空间换时间的算法

注意:本文图文并茂

将提供以下图文链接供大家理解:
图文链接:
飞书图解链接🎉🎉🎉
密码:67&2Z172

前缀和

定义
前缀和可以简单理解为「数列的前 n 项的和」,是一种重要的预处理方式,能大大降低查询的时间复杂度。

一维前缀和

题目一

Luogu P8218 【深进1.例1】求区间和

AC代码,展开查看
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N], s[N];
int main(){
    int n, m;
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++ ) {
        scanf("%d", &a[i]);
        s[i] = s[i - 1] + a[i];
    }
    scanf("%d", &m);
    while(m -- ){
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", s[r] - s[l - 1]);
    }
    return 0;
}

题目二

Acwing 795. 前缀和

AC代码,展开查看
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N], s[N];
int main(){
    int n, m, l, r;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++ ) {
        scanf("%d", &a[i]);
        s[i] = s[i - 1] + a[i];
    }
    while(m -- ){
        scanf("%d%d", &l, &r);
        printf("%d\n", s[r] - s[l - 1]);
    }
    return 0;
}

二维前缀和

题目一

AcWing 796. 子矩阵的和

AC代码,展开查看
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int n, m, q;
int a[N][N];
int main(){
    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]);
            a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
        }
    }
    int x1, y1, x2, y2;
    while(q -- ){
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        printf("%d\n", a[x2][y2] - a[x2][y1 - 1] - a[x1 - 1][y2] + a[x1 - 1][y1 - 1]);
    }
    return 0;
}

题目二

Luogu P2280 [HNOI2003] 激光炸弹

AC代码,展开查看
#include<bits/stdc++.h>
using namespace std;
const int N = 5e3 + 2;
int s[N][N];
int main(){
    int n, m, x, y, v;
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i ++ ){
        scanf("%d%d%d", &x, &y, &v);
        x ++ , y ++ ;
        s[x][y] += v; // 每个攻击目标都具有v价值,攻击目标有可能重复
    }
    for(int i = 1; i < N; i ++ ){
        for(int j = 1; j < N; j ++ ){
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
        }
    }
    int res = 0;
    for(int i = m; i < N; i ++ ){
        for(int j = m; j < N; j ++ ){
            res = max(res, s[i][j] - s[i - m][j] - s[i][j - m] + s[i - m][j - m]);
        }
    }
    printf("%d", res);
    return 0;
}

差分

定义
差分是一种和前缀和相对的策略,可以当做是求和的逆运算。

一维差分

题目一

Acwing 797. 差分

AC代码,展开查看
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int main(){
    int n, m, l, r, c, t;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++ ){
        scanf("%d", &t);
        a[i] += t; // 求差分数组, 相当于b[i] = a[i] - a[i - 1];
        a[i + 1] -= t;
    }
    while(m -- ){
        scanf("%d%d%d", &l, &r, &c);
        a[l] += c;
        a[r + 1] -= c;
    }
    for(int i = 1; i <= n; i ++ ){
        a[i] += a[i - 1];
        printf("%d ", a[i]);
    }
}

题目二

Luogu P4552 [Poetize6] IncDec Sequence

AC代码,展开查看
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int a[N];
int main(){
    int n, t;
    scanf("%d", &n);
    for(int i = 0; i < n; i ++ ){
        scanf("%d", &t);
        a[i] += t, a[i + 1] -= t;
    }
    LL p = 0, q = 0;
    for(int i = 1; i < n; i ++ ){
        if(a[i] > 0) p += a[i]; // 正数总和
        else q += a[i]; // 负数总和
    }
    q = abs(q); // 求负数总和的绝对值
    printf("%ld\n%ld", max(p, q), abs(p - q) + 1);
    return 0;
}

二维差分

题目一

AcWing 798. 差分矩阵
解法一:

AC代码,展开查看
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int a[N][N];
int main(){
    int n, m, q, x1, y1, x2, y2, c, t;
    scanf("%d%d%d", &n, &m, &q);
    for(int i = 1; i <= n; i ++ ){
        for(int j = 1; j <= m; j ++ ){
            scanf("%d", &t);
            a[i][j] += t, a[i][j + 1] -= t;
        }
    }
    while(q -- ){
        scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);
        for(int i = x1; i <= x2; i ++ ){
            a[i][y1] += c, a[i][y2 + 1] -= c;
        }
    }
    for(int i = 1; i <= n; i ++ ){
        for(int j = 1; j <= m; j ++ ){
            a[i][j] += a[i][j - 1];
            printf("%d ", a[i][j]);
        }
        puts("");
    }
    return 0;
}

这种方法本质上是一维差分,可以AC,但是花费3s

解法二:

AC代码,展开查看
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int a[N][N];
void insert(int x1, int y1, int x2, int y2, int c){
    a[x1][y1] += c;
    a[x2 + 1][y1] -= c;
    a[x1][y2 + 1] -= c;
    a[x2 + 1][y2 + 1] += c;
}
int main(){
    int n, m, q, t;
    scanf("%d%d%d", &n, &m, &q);
    for(int i = 1; i <= n; i ++ ){
        for(int j = 1; j <= m; j ++ ){
            scanf("%d", &t);
            insert(i, j, i, j, t);
        }
    }
    int x1, y1, x2, y2, c;
    while(q -- ){
        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 ++ ){
            a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
            printf("%d ", a[i][j]);
        }
        puts("");
    }
    return 0;
}

题目二

Luogu P3397 地毯
解法1:

AC代码,展开查看
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int a[N][N];
int main(){
    int n, m, x1, y1, x2, y2;
    scanf("%d%d", &n, &m);
    while(m -- ){
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        for(int i = x1; i <= x2; i ++ ){
            a[i][y1] ++ , a[i][y2 + 1] -- ;
        }
    }
    for(int i = 1; i <= n; i ++ ){
        for(int j = 1; j <= n; j ++ ){
            a[i][j] += a[i][j - 1];
            printf("%d ", a[i][j]);
        }
        puts("");
    }
    return 0;
}

解法2:

AC代码,展开查看
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int a[N][N];
void insert(int x1, int y1, int x2, int y2, int c){
    a[x1][y1] += c;
    a[x2 + 1][y1] -= c;
    a[x1][y2 + 1] -= c;
    a[x2 + 1][y2 + 1] += c;
}
int main(){
    int n, m, x1, y1, x2, y2;
    scanf("%d%d", &n, &m);
    while(m -- ){
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        insert(x1, y1, x2, y2, 1);
    }
    for(int i = 1; i <= n; i ++ ){
        for(int j = 1; j <= n; j ++ ){
            a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
            printf("%d ", a[i][j]);
        }
        puts("");
    }
    return 0;
}

第二种方法更快,快了1ms.🤣

本文参考自【董晓算法的个人空间-哔哩哔哩】

海纳百川,有容乃大!如果文章有什么不足之处,还请大神们评论区留言指出,我在此表达感谢🥰!若大家喜欢我的作品,欢迎点赞、收藏、打赏🎉🎉🎉!文章来源地址https://www.toymoban.com/news/detail-747028.html

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

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

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

相关文章

  • 前缀和&差分算法(Python版)

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

    2024年04月17日
    浏览(54)
  • 算法基础之差分和前缀和

    结论:差分是前缀和的逆运算 举例 一维差分 二维差分 用在一维子区间里的数都增减一个固定值,把对于区间内每个数的操作转换为对于差分数组中的端点的操作,时间复杂度降为o(1)。 用在二维子矩阵里的数都增减一个固定值,把对于子矩阵的每个数的操作转换为对应差分

    2024年02月07日
    浏览(46)
  • 【算法基础】前缀和与差分

    😽 PREFACE 🎁欢迎各位→点赞 👍 + 收藏 ⭐ + 评论 📝 📢系列专栏: 算法 💪 种一棵树最好是十年前其次是现在 前缀和指一个数组的某下标之前的所有数组元素的和(包含其自身)。前缀和分为一维前缀和,以及二维前缀和。前缀和是一种重要的预处理,能够降低算法的时

    2024年01月19日
    浏览(35)
  • 【算法】—前缀和与差分详解

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

    2024年02月04日
    浏览(55)
  • 第四章:前缀和、差分(数列)

    在解释什么是前缀和之前,我们先回顾一下高中学过的数列: 我们这里所说的前缀和其实就是我们在高中学的数列中的 Sn(前n项和) ,只是我们这里需要将 S1 , S2 , S3 , S4 …… Sn 当作一个新的数组。 为了这个式子的高度统一性,我们的S0和a0都是不存储数据的,将其设置为0,这

    2023年04月08日
    浏览(35)
  • 【算法基础2】前缀和与差分

    前缀和是某数列的前n项数的和,而差分则可以看做是前缀和的逆运算。前缀和与差分比起是一种算法,更像是一种解决问题的思路,通过构造一个特殊的数组,就可以让我们将某些复杂的问题简化。 (1)一维前缀和 已知一个数列a[n],用S[n]来表示这个数列的前n项和数列。

    2024年04月14日
    浏览(43)
  • C/C++ 前缀和与差分

    个人主页:仍有未知等待探索_C语言疑难,数据结构,算法-CSDN博客 专题分栏:算法_仍有未知等待探索的博客-CSDN博客 目录 一、前言 1、什么是前缀和 2、什么是差分 3、优势 1.朴素做法: 2.用差分数组 二、代码实现 1、给一个数组去求其差分数组 2、给一个数组去求其前缀和数

    2024年02月03日
    浏览(39)
  • C++基础算法前缀和和差分篇

    📟作者主页:慢热的陕西人 🌴专栏链接:C++算法 📣欢迎各位大佬👍点赞🔥关注🚓收藏,🍉留言 主要讲解了前缀和和差分算法 Ⅵ .Ⅰ前缀和 ① 一维前缀和 : ​ 就是构建一个新的数组 s ,用来存储另一个数组的和前 i 个数组元素的和。用公式表达就是: S [ i ] = a [ 0 ]

    2024年02月16日
    浏览(52)
  • 【algorithm】认真讲解前缀和与差分 (图文搭配)

    🚀write in front🚀 📝个人主页:认真写博客的夏目浅石. 📣系列专栏:AcWing算法笔记 今天的月色好美 这里介绍以下前缀和算法以及差分算法,用来梳理自己所学到的算法知识。 从我的理解角度来讲:前缀和就是高中数学当中的数列的求和Sn,差分就是前缀和的逆运算,就是

    2024年01月21日
    浏览(41)
  • 【OI学习笔记】基础算法-前缀和与差分算法

    板块:基础算法、线性优化 难度:较易 前置知识:C++基础语法 在一维空间中,对于一个数据总量为 n n n 的数组 a a a ,有数据 a [ 1 ] , a [ 2 ] , a [ 3 ] , . . . , a [ n − 1 ] , a [ n ] a[1],a[2],a[3],...,a[n-1],a[n] a [ 1 ] , a [ 2 ] , a [ 3 ] , ... , a [ n − 1 ] , a [ n ] ,定义一个数组 s u m sum s u m ,

    2024年02月08日
    浏览(51)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包