首页 > 其他分享 >C语言——前缀和，差分

C语言——前缀和，差分

时间：2025-01-22 12:02:43浏览次数：3  
标签：origin 前缀 int 差分 C语言 vector 数组 difference

  • 前缀和

一维前缀和（One-dimensional prefix sum）

所谓一维，实际上就是一维数组，数组元素连续排列就可以看做一维的线，一维前缀和解决的主要问题是一维数组的区间和问题，即给定双指针l,r，求原数[l，r]内的和，利用数学上的数列来解决，即S_{r}-S_{l-1}。(a_{l}+a_{l+1}+......+a_{r-1}+a_{r})

构建一维前缀和：

由S_{r}-S_{l}易知至少存在两个数值，所有我们把prefixsum[0]初始化为0，其后任意元素（第n个元素，n为正整数）减去prefixsum[0]得前n项和S_{n}。

prefixsum数组的每一个元素都是每个n对应的S_{n}=S_{n-1} + a_{n}。

origin是从0索引开始的origin【i-1】对应第i个数

void Buildprefixsum1D(vector<int>& origin,vector<int>& prefixsum,int n) {
    prefixsum[0]=0;
    for(int i=1;i<=n;i++) {
        prefixsum[i]=prefixsum[i-1]+origin[i-1];
    }
}
求区间和：

S_{n}中包含a_{n}，所有如果只求得a_{n}=S_{n} -  S_{n-1}。

求原数[l，r]内的和，利用数学上的数列来解决，即S_{r}-S_{l-1}。(a_{l}+a_{l+1}+......+a_{r-1}+a_{r})

void S(int l,int r,vector<int>& prefixsum) {
    cout<<prefixsum[r]-prefixsum[l-1]<<endl;
}
 总代码：

根据洛谷区间和例题P8218

#include<iostream>
#include<vector>
using namespace std;
void Buildprefixsum1D(vector<int>& origin,vector<int>& prefixsum,int n) {
    prefixsum[0]=0;
    for(int i=1;i<=n;i++) {
        prefixsum[i]=prefixsum[i-1]+origin[i-1];
    }
}
void S(int l,int r,vector<int>& prefixsum) {
    cout<<prefixsum[r]-prefixsum[l-1]<<endl;
}
int main() {
    int n,m;
    cin>>n;
    vector<int> origin(n);
    for(int i=0;i<n;i++) {
        cin>>origin[i];
    }//初始化原数组
    vector<int> oneDprefixsum(n+1);
    Buildprefixsum1D(origin,oneDprefixsum,n);
    cin>>m;
    for(int i=0;i<m;i++) {
        int l,r;
        cin>>l>>r;
        S(l,r,oneDprefixsum);
    }
    return 0;
}

  • 二维前缀和（Two-dimensional prefix sum）

二维前缀和的作用是求“面积”，首先我们有一个原始二位数组（origin[n][m]），这个二维数组可以看做二维平面，即由正方形组成的长为m，宽（高）为n的网格矩形，在此处引入一个新的二维数组prefixsum1D[n+1][m+1]，这个数组内的元素S_{i,j}代表以左上角（0,0）为一个左上端点，（i，j）为右下端点的矩形内原数组origin内所有在i，j矩形内元素的和。

如下图，原始数组的示意图，每个方格代表一个元素，而二位前缀和数组内的元素S_{i,j}代表一片面积，令i=2，j=2，则S_{i,j}的值就是图中所有元素的和，若i=1，j=2。则S_{i,j}就是前2行所有数字的和。所有二位前缀和也被称作求面积。

首先给出公式：s代表二维前缀和，a代表原始数组

s[i][j]=s[i][j-1]+s[i-1][j]-s[i-1][j-1]+a[i][j]

下图中，红色部分为（i，j），欲求前缀和S（i，j），绿色部分是S（i，j-1），蓝色部分是

S（i-1，j），紫色部分（i-1，j-1）我们求的S（i，j）实际上就是左上角4个正方形的元素的和，也就是一片面积，

s[i][j]=绿色+蓝色-紫色+红色

 

不难发现，计算 S_{i,j}需要先获取3块面积（如果红色正方形也算入是4块面积，但红色数值已知），所有在二维前缀和数组prefixsum2D中要将第一行和第一列初始化为0。

构建二维前缀和数组：

这一次为了方便理解防止混淆，我们的原始数组origin是从1,1开始的，第一行和第一列都默认是0了（也就是说当做第一行第一列不存在了<实际上是0行0列不存在了>），这样原始数组和二维前缀和数组是重合的。

void Buildprefixsum2D(vector<vector<int>> &origin,int n,int m,vector<vector<int>> &prefixsum2D) {
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            prefixsum2D[i][j]=prefixsum2D[i-1][j]+prefixsum2D[i][j-1]-prefixsum2D[i-1][j-1]+origin[i][j];
        }
    }
}

欲求不以1,1为起点的面积，如图

欲求红色部分，有公式

红色=s[i][j]-s[i][b-1]-s[a-1][j]+s[a-1][b-1]

红色=S[i,j]-蓝色-绿色+紫色

如果只是求单一正方形的值（origin的元素只需令i=a，j=b即可）

 求面积：
int S(vector<vector<int>> &prefixsum2D,int i,int j,int a,int b) {
    return prefixsum2D[i][j]-prefixsum2D[i][b-1]-prefixsum2D[a-1][j]+prefixsum2D[a-1][b-1];
}
总代码：

以洛谷例题P1719为例

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
void Buildprefixsum2D(vector<vector<int>> &origin,int n,int m,vector<vector<int>> &prefixsum2D) {
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            prefixsum2D[i][j]=prefixsum2D[i-1][j]+prefixsum2D[i][j-1]-prefixsum2D[i-1][j-1]+origin[i][j];
        }
    }
}
int S(vector<vector<int>> &prefixsum2D,int i,int j,int a,int b) {
    return prefixsum2D[i][j]-prefixsum2D[i][b-1]-prefixsum2D[a-1][j]+prefixsum2D[a-1][b-1];
}
int main() {
    int n,m,ans;
    cin>>n;
    m=n;
    vector<vector<int>> origin(n+1,vector<int>(m+1));
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            cin>>origin[i][j];
        }
    }
    vector<vector<int>> prefixsum2D(n+1,vector<int>(m+1,0));
    Buildprefixsum2D(origin,n,m,prefixsum2D);
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            for(int a=1;a<i;a++) {
                for(int b=1;b<j;b++) {
                    ans=max(S(prefixsum2D,i,j,a,b),ans);
                }
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

  • 差分

  • 一维差分（One-dimensional difference）

所谓差分，其实就是两个数的差，原数组每一个a_{i}-a_{i-1}就是每个差分数组的b_{i}。

实际上原数组是差分数组的前缀和，差分元素有正有负，使得差分的和被调整为原数组的元素。

差分的基本作用就是给一个区间的数进行加减处理，比如让【l，r】内都加上c，可以使原本

O（n）变为O（1），大大提高效率。

构建差分数组：
void Builddifference(vector<int> &prefixsum,int n,vector<int> &difference) {
    for(int i=1;i<=n;i++) {
        difference[i] = prefixsum[i] - prefixsum[i-1];
    }
}
实现区间内的统一加减运算：

根据前缀和，如果在b_{l}也就是a_{l}-a_{l-1} 上加C，那从n=0开始累加，在n=l后的每一个原数组元素（前缀和）都增加了C，同理对b_{r+1}减去C，那n=r+1后的每个原数组元素（前缀和）都减去C，抵消掉了原来的+C。

void function(vector<int> &difference,int l,int r,int c) {
    difference[l] +=c;
    difference[r+1] -=c;
}
总代码：

以洛谷例题P2367为例

#include<iostream>
#include<vector>
using namespace std;
void Builddifference(vector<int> &prefixsum,int n,vector<int> &difference) {
    for(int i=1;i<=n;i++) {
        difference[i] = prefixsum[i] - prefixsum[i-1];
    }
}
void function(vector<int> &difference,int l,int r,int c) {
    difference[l] +=c;
    difference[r+1] -=c;
}
int main() {
    int n,p;
    cin>>n>>p;
    vector<int> prefixsum(n+1);
    prefixsum[0] = 0;
    for(int i=1;i<=n;i++) {
        cin>>prefixsum[i];
    }
    vector<int> difference(n+1);
    Builddifference(prefixsum,n,difference);
    for(int i=1;i<=p;i++) {
        int l,r,c;
        cin>>l>>r>>c;
        function(difference,l,r,c);
    }
    int ans=difference[1],temp=0;
    for(int i=1;i<=n;i++) {
        temp+=difference[i];
        ans=min(ans,temp);
    }
    cout<<ans<<endl;
    return 0;
}

  • 二维差分（Two-dimensional difference）

二维差分实际上是使用了二维前缀和，对差分数组进行前缀和，以左上角为起点，（i，j）为右下角的终点，所得的面积就是原数组在（i，j）的元素值。

初始化：

初始化的过程其实就是进行加减C的过程，但实际是一类特殊情况，即只对一个元素进行操作，保证其他元素不受影响。（用c表a【i】【j】）

 

通过以上4次操作，使得只 b【i】【j】加上了C，也就是只有一块面积（一个正方形格子）加上了C。

根据公式易知操作数i，j存在，但i+1，j+1不一定存在，所以二维差分数字最外围一圈都是0。（方便对应并且防止溢出）

void Insert(vector<vector<int>> &initial,vector<vector<int>> &difference,int n,int m) {
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            difference[i][j]+=initial[i][j];
            difference[i+1][j]-=initial[i][j];
            difference[i][j+1]-=initial[i][j];
            difference[i+1][j+1]+=initial[i][j];
        }
    }
}
矩形整体加减运算：

 实际上是广泛化的初始化，原理相同。

void function(vector<vector<int>> &difference,int x1,int y1,int x2,int y2,int c) {
    difference[x1][y1]+=c;
    difference[x2+1][y1]-=c;
    difference[x1][y2+1]-=c;
    difference[x2+1][y2+1]+=c;
}
输出结果：

 实际上就是进行二维前缀和

void Print(vector<vector<int>> &initial,vector<vector<int>> &difference,int n,int m) {
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            difference[i][j]=difference[i-1][j]+difference[i][j-1]-difference[i-1][j-1]+difference[i][j];
            initial[i][j]=difference[i][j];
            cout<<initial[i][j]<<" ";
        }
        cout<<endl;
    }
}
总代码：

以洛谷例题P3397为例

#include<iostream>
#include<vector>
using namespace std;
void Insert(vector<vector<int>> &initial,vector<vector<int>> &difference,int n,int m) {
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            difference[i][j]+=initial[i][j];
            difference[i+1][j]-=initial[i][j];
            difference[i][j+1]-=initial[i][j];
            difference[i+1][j+1]+=initial[i][j];
        }
    }
}
void function(vector<vector<int>> &difference,int x1,int y1,int x2,int y2,int c) {
    difference[x1][y1]+=c;
    difference[x2+1][y1]-=c;
    difference[x1][y2+1]-=c;
    difference[x2+1][y2+1]+=c;
}
void Print(vector<vector<int>> &initial,vector<vector<int>> &difference,int n,int m) {
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            difference[i][j]=difference[i-1][j]+difference[i][j-1]-difference[i-1][j-1]+difference[i][j];
            initial[i][j]=difference[i][j];
            cout<<initial[i][j]<<" ";
        }
        cout<<endl;
    }
}
int main() {
    int n,m,p;
    cin>>n>>p;
    m=n;
    vector<vector<int>> initial_array(n+2,vector<int>(m+2,0));
    vector<vector<int>> difference(n+2,vector<int>(m+2,0));
    /*for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            cin>>initial_array[i][j];
        }
    }
    Insert(initial_array,difference,n,m);例题初始都为0无需初始化*/
    for(int i=0;i<p;i++) {
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        function(difference,x1,y1,x2,y2,1);
    }
    Print(initial_array,difference,n,m);
    return 0;
}

标签：origin,前缀,int,差分,C语言,vector,数组,difference
From： https://blog.csdn.net/2401_88542533/article/details/145281773

相关文章

  • 22. C语言 输入与输出详解
    本章目录:前言1.输入输出的基础概念1.1标准输入输出流1.2输入输出函数2.格式化输出与输入2.1使用`printf()`进行输出示例1:输出字符串示例2:输出整数示例3:输出浮点数2.2使用`scanf()`进行输入示例4:读取整数和字符改进方案：使用`getchar()`清理缓冲......
  • 21. C语言 `typedef`：类型重命名
    本章目录:前言1.什么是`typedef`？语法示例：基本类型的别名2.`typedef`为结构体定义别名示例：为结构体定义别名3.`typedef`vs`#define`：两者的区别(1)**作用范围和处理方式**(2)**类型别名的处理**(3)**多个变量的声明**(4)**宏展开与编译器处理**4.`typedef`......
  • 20. C语言 位域（Bit-field）
    本章目录:前言什么是位域？如何定义位域？示例位域的内存分配位域的使用场景节省内存网络协议文件解析位域的限制位域的常见错误进阶示例：位域与指针总结前言在C语言中，位域（Bit-field）是一种特殊的结构体成员，它允许我们按位定义成员的大小。这对于存储具有明确大小限制......
  • C语言的循环结构
    循环结构是编程语言中的一种重要结构，用于重复执行一段代码。主要有三种循环结构：for循环，while循环和do-while循环。循环结构(1)当型循环结构：当条件P成立(为真)时，反复执行循环语句，直到条件P不成立(为假)时结束循环。（条件成立，才执行循环语句，for、while）(2)直到型循环结构：先......
  • C语言/C++——递归、递推、动态规划
    什么是动态规划：给定一个问题，我们把他拆成一个个子问题，直到子问题可以直接解决。然后把子问题的答案保存起来，以减少重复计算。再根据子问题的答案反推，得出原问题解的一种方法递归的过程："递"的过程是分解子问题的过程；（dfs是第归的一种）            “归......
  • 数据结构之链表（linked list）代码实现(小白轻松懂，C语言版)
    一、前言：链表的简单介绍链表（LinkedList）是一种重要的线性数据结构，它以节点（Node）的形式存储数据，每个节点通过指针（或引用）指向下一个节点，从而形成一个动态的数据链条。与数组不同，链表的内存分配并不连续，因此具有更灵活的插入和删除操作，但在随机访问元素时效率相对较低。链表通......
  • C语言的那点事第五篇：编程界的“外卖小哥”函数
    函数就像是编程界的“外卖小哥”，帮你把任务分解成小块，然后把结果送回来。别担心，我会用幽默的方式带你飞驰在这个奇妙的世界里。咱们开始吧！1.函数定义与调用外卖小哥的职责：想象一下，你每天都要做饭，但每次都从头开始，那得多累啊！函数就像是你的“外卖小哥”，帮你把任务分解成小......
  • C语言中的二维数组
    1.二维数组的定义类型说明符数组名 [常量表达式][常量表达式];(1).类型说明符      表示二维数组中数据元素的类型 (2).数组名          标识符 (3).[常量表达式][常量表达式]      第1维       第2维   ......
  • C语言程序设计十大排序—冒泡排序
    文章目录1.概念✅2.冒泡排序......
  • C语言编译
    C语言编译是把C语言编写的源代码转换为计算机能执行的机器码的过程。 首先需要一个文本编辑器来写代码，比如Vim、Notepad++等。代码写好后，使用C编译器，常见的有GCC（GNUCompilerCollection）。以GCC为例，如果有一个名为 main.c 的源文件，在命令行中输入 gccmain.c-ooutput ......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99