Acwing 前缀与差分

🕗 发布于 2024-10-14 23:16 算法

1.一维前缀和

一维前缀和：S[i]=a1+a2+a3+a4+…+ai，要求a从a1开始，且S[0]=0

前缀和的作用：给定一组序列数据，可以计算任意第l个数到第r个数的和，S[r]-S[l-1]（这里就解释了为什么要求S[0]=0，因为当l=1时，实质就是求是S[r]）
求很多个任意子序列的数据和时，假如不使用前缀和公式，就需要顺序遍历来求，时间复杂度为O(n)
使用前缀和，直接得到结果，时间复杂度为O(1)

Acwing 795.前缀和
在这里插入图片描述
具体实现代码（详解版）：

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;
int a[N],s[N];
int n,m;

int main(){
    cin >> n >> m;
    
    for(int i = 1 ; i <= n ; i ++) cin >> a[i];
    for(int i = 1 ; i <= n ; i ++) s[i] = s[i - 1] + a[i];//计算前缀和，s[0] = 0
    
    //处理询问
    while(m --){
        int l , r;
        cin >> l >> r;
        
        cout << s[r] - s[l - 1] << endl;//使用前缀和
    }
    
    return 0;
}

2.二维前缀和

在这里插入图片描述
二维前缀和：S[i][j]即为坐标(i,j)左上部分所有元素的和，也就是绿色区域的所有元素和（注意i，j依旧是从1开始，s[0][0]默认为0）

二维前缀和计算公式：s[i][j]=s[i][j-1]+s[i-1][j]-s[i-1][j-1]+a[i][j]（注意这里要s[i][j-1]+s[i-1][j]多算了一次s[i-1][j-1]，所以要减去一次）
在这里插入图片描述
任意子矩阵中所有数的和计算：

设所求子矩阵的左上角坐标为(x1,y1)，右下角坐标为(x2,y2)

s=s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]

eg:s=S[5][3] - S[2][3] - S[5][1] + S[2][1]

在这里插入图片描述
具体实现代码（详解版）：

#include <iostream>

using namespace std;

const int N = 1010; 

int a[N][N], s[N][N]; // a 用于存储原始矩阵，s 用于存储二维前缀和
int n, m, q; // n: 行数, m: 列数, q: 查询的次数

int main() {
   
    cin >> n >> m >> q;
    
   
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
    
    // 计算前缀和矩阵 s
    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];
        }
    }
    
    // 处理 q 次查询
    while (q--) {
        int res = 0; // 存储子矩阵的和
        int x1, y1, x2, y2; // 子矩阵左上角 (x1, y1) 和右下角 (x2, y2)
        
        cin >> x1 >> y1 >> x2 >> y2;
        
        // 利用前缀和公式计算子矩阵的和
        res = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
        
        cout << res << endl;
    }
    
    return 0;
}

3.一维差分

差分的实质是前缀和的逆运算
假设有一个数组，a{1}，a{2}，a{3}，a{4}，a{5}，…，a{n}
针对这个数组，构造出另一个数组，b{1}，b{2}，b{3}，b{4}，b{5}，…，b{n}
使得a数组是b数组的前缀和，即使得 a{i} = b{1} + b{2} + … + b{i}；b{i}=a{i}-a{i-1}

差分的作用：
若要对a数组中[l, r]区间内的全部元素都加上一个常数C，若直接操作a数组的话，需要循环遍历，时间复杂度是O(n)。而如果操作其差分数组b，则时间复杂度是O(1)。即可以用O(1)的时间给某一数组的某一子序列元素都加上一个值
具体实现：
数组a是数组b的前缀和数组，只要对 b{l}这个元素加C，则a数组从l位置之后的全部数都会被加上C，但r位置之后的所有数也都加了C，所以我们通过对 b{r+1} 这个数减去C，来保持a数组中r位置以后的数的值不变，即a数组r位置以后的数都是+C-C抵消。
于是，对a数组的[l, r]区间内的所有数都加上一个常数C，就可以转变为对 b{l}+C，对b{r+1}-C。
对于构造差分数组b：
在输入数组a时，可以先假想数组a和数组b的全部元素都是0。然后每次进行一次插入操作（指的是对数组a的[l, r]区间的每个数加上常数C），比如对a数组区间[1,1]，加（插入）常数a{1}，效果就是 b{1}=b{1}+a{1}，b{2}=b{2}-a{1}；对区间[2,2]，加常数a{2}，效果就是 b{2}=b{2}+a{2}，b{3}=b{3}-a{2},…，这样在输入数组a的同时，就能够快速构造出其差分数组b。实际就把构造数组b的过程看作为给一个数组中[l, r]区间内的全部元素都加上一个常数C的过程，只不过特殊的是这个数组元素都为0，这个区间为[i,i]，这个常数C会变化为a[i]

具体实现代码（详解版）：

#include <iostream>

using namespace std;

const int N = 1e6 + 10; 

int a[N], b[N]; // a 用于存储初始数组，b 为差分数组
int n, m; // n: 数组大小, m: 操作次数

// 插入操作，差分数组的更新
void insert(int l, int r, int c) {
    b[l] += c;       // 在区间左端点加上 c
    b[r + 1] -= c;   // 在区间右端点的下一个位置减去 c
}

int main() {
    cin >> n >> m;

    // 读取初始数组 a 的值，并将其转换为差分数组 b
    for (int i = 1; i <= n; i++) {
        cin >> a[i];      // 读入初始数组
    }
    for (int i = 1; i <= n; i++) {
        insert(i, i, a[i]);  // 将初始数组 a 构造成差分数组 b
    }
    
    // 处理 m 次操作
    while (m--) {
        int l, r, c;
        cin >> l >> r >> c; // 读入操作：对区间 [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++) {
        cout << b[i] << ' ';  
    }
    cout << endl; // 换行
    
    return 0;
}

4.二维差分

类比一维差分和二维前缀和，二维差分的作用：以时间复杂度O(1)对任意子矩阵加上一个常数
具体实现：

期望对矩阵a中左上角为[x1, y1]，右下角为[x2, y2]的区域内的全部元素，都加一个常数C，则可以转化为对其差分矩阵b的操作。
先对b中[x1, y1]位置上的元素加C，这样以来，前缀和a中[x1, y1]这个点的右下角区域内的所有数都加上了C，但是这样就对[x2, y2]之后的区域也都加了C。我们对[x2, y2]之外的区域需要保持值不变，所以需要进行减法。对b{x2+1,y1} 减掉C，这样下图红色区域都被减了C，再对b{x1,y2+1}减掉C，这样下图蓝色区域都被减了C，而红色区域和蓝色区域有重叠，重叠的区域被减了2次C，所以要再加回一个C，即对b{x2+1,y2+1}加上一个C。这样，就完成了对[x1,y1]，[x2, y2]区域内的所有数（下图绿色区域），都加上常数C。

构造差分二维数组b
思想和一维差分一样，假设二维数组a和二维数组b初始化都为0，在输入a[i][j]时就可顺便构造b[i][j]。实际就把构造数组b的过程看作为给一个数组中[x1, y1]，[x2, y2]区域内的全部元素都加上一个常数C的过程，只不过特殊的是这个数组元素初始都为0，这个区域为[i,j]到[i,j]（即就是一个元素），这个常数C会变化为a[i][j]

具体实现代码（详解版）：

#include <iostream>

using namespace std;

const int N = 1010;

int a[N][N], b[N][N]; // a 用于存储原始矩阵，b 用于存储差分矩阵
int n, m, q;

// 插入操作：更新差分矩阵 b，反映在子矩阵 (x1, y1) 到 (x2, y2) 中加上常数 c 的操作
void insert(int x1, int y1, int x2, int y2, int c) {
    b[x1][y1] += c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y1] -= c;
    b[x2 + 1][y2 + 1] += c;
}

int main() {
    cin >> n >> m >> q;
    
    // 输入原始矩阵 a
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
    
    // 构造差分矩阵 b，基于初始矩阵 a
    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;
        cin >> 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] + b[i][j];
        }
    }
    
    // 输出更新后的最终矩阵
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cout << b[i][j] << ' ';
        }
        cout << endl;
    }
    
    return 0;
}

以上就是前缀和差分的基本应用，前缀和除了在这里和差分一起使用外，后续还会有应用。（主要的就说要推导并记住一维和二维前缀和的公式）

s[i] = s[i] + a[i];//计算一维前缀和
res = s[r] - s[l-1];//计算l-r的区间和

s=s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];//计算二维前缀和
res = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]; 利用前缀和公式计算子矩阵的和

差分的重点是构造差分数组：

//一维
// 插入操作，差分数组的更新
void insert(int l, int r, int c) {
    b[l] += c;       // 在区间左端点加上 c
    b[r + 1] -= c;   // 在区间右端点的下一个位置减去 c
}
...
insert(i, i, a[i]);  // 将初始数组 a 构造成差分数组 b

//二维
// 插入操作：更新差分矩阵 b，反映在子矩阵 (x1, y1) 到 (x2, y2) 中加上常数 c 的操作
void insert(int x1, int y1, int x2, int y2, int c) {
    b[x1][y1] += c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y1] -= c;
    b[x2 + 1][y2 + 1] += c;
}
...
 insert(i, j, i, j, a[i][j]);// 构造差分矩阵 b，基于初始矩阵 a

原文地址：https://blog.csdn.net/qq_43060884/article/details/142914751

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：Java 高级开发需要会哪些技术？
下一篇：leetcode数组（一）--二分查找

leetcode289:生命游戏
根据，简称为，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。给定一个包含m × n个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态：1即为（live），或0即为
阅读更多2024-10-20
MongoDB数据恢复
注意：两个MongoDB的版本要一致，本文使用的是mongo:4.2.24。先把K8S上面的MongoDB 容器停止（可以把副本改成0）。1、将容器挂载MongoDB的数据目录备份到本地。经常是数据文
阅读更多2024-10-20
C#中实现事务
C#中实现事务
阅读更多2024-10-20
【LeetCode每日一题】——560.和为 K 的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的子数组的个数。子数组是数组中元素的连续非空序列。
阅读更多2024-10-20
「漏洞复现」满客宝智慧食堂系统 selectUserByOrgId 未授权访问漏洞
请勿利用文章内的相关技术从事非法测试，由于传播、利用此文所提供的信息而造成的任何直接或者间接的后果及损失，均由使用者本人负责，作者不为此承担任何责任。工具来自网络，安全性自测，如有侵权请联系删除。本次
阅读更多2024-10-20
React面试题目（从基本到高级）
React前端面试常见题目涵盖了React的基础概念、组件、状态管理、生命周期、性能优化等多个方面。
阅读更多2024-10-20
12.个人博客系统（Java项目基于spring和vue）
1 在校学习的学生，可用于日常学习使用或是毕业设计使用 2 毕业一到两年的开发人员，用于锻炼自己的独立功能模块设计能力，增强代码编写能力。 3 亦可以部署为商化项目使用。 4 需要完整资料及源码
阅读更多2024-10-20
YoloV8改进策略：注意力改进|DeBiFormer，可变形双级路由注意力|引入DeBiLevelRoutingAttention注意力模块（全网首发）
本次改进的核心在于将DeBiLevelRoutingAttention模块嵌入到YoloV8的主干网络中，具体位置是在SPPF（Spatial Pyramid Pooling Fast）模块之后。这一
阅读更多2024-10-20
word取消自动单词首字母大写
情况说明：在word输入单词后首字母会自动变成大写取消单词首字母大写步骤：（1）点击菜单栏文件（2）点击“更多”——>“选项”（3）点击“校对”——>“自动更正选项”（4）取消“句首字母大
阅读更多2024-10-20
web前端网页用户注册页面
【代码】web前端网页用户注册页面。
阅读更多2024-10-20

Acwing 前缀与差分

1.一维前缀和

2.二维前缀和

3.一维差分

4.二维差分

相关文章