当前位置: 首页 > news >正文

前缀和与差分(一维)

一维前缀和与一维差分

一维前缀和

假如我们需要求一个数组的[L,R]这个区间的区间和,假如说我们要访问q次,我们能想到的就是暴力的去计算每一组的和,这样的时间复杂度为O(n*q)假如我们的q和n非常大那么这个时间复杂度是不太行的,所以我们要用到前缀和数组
在这里插入图片描述
我们现在知道前缀和数组存储的是[0,R]区间的和,那么我们怎么得到[L,R]区间的和呢?我们发现可以让[0,R]的区间和减去[0,L]的区间和
在这里插入图片描述

代码如下

#include<iostream>
using namespace std;
const int N = 5;
int sum[N];
//#define get_sum(L,R) (L?sum[R]-sum[L-1]:sum[R])
int get_sum(int L, int R)
{if (L != 0){return sum[R] - sum[L - 1];}return sum[R];
}
int main()
{int n = 5;int arr[N] = { 1,3,5,7,2 };sum[0] = arr[0];for (int i = 1; i < n; i++){sum[i] = sum[i - 1] + arr[i];}for (int i = 0; i < n; i++){cout << sum[i] << " ";}cout << endl;cout << get_sum(0, 3) << endl;cout << get_sum(2, 4) << endl;return 0;
}

一维前缀和模板

sum[0] = arr[0];
for (int i = 1; i < n; i++)
{sum[i] = sum[i - 1] + arr[i];
}

一维差分

给定一个n个数的数组arr[1,3,7,5,2] 我们需要m个操作 需要在区间[L,R]中每一个数都加上val,最后询问数组arr中的元素是怎样的?
在这里插入图片描述
我们遍历数组的每一个元素然后每遍历一次就加上对应的数值此时时间复杂度为O(n*m),那如何去优化呢?

我们可以看到对与下标为2的数7他被操作了三次其最后结果其实就是7+(5+2-4)=10就是7+3=10,那我们是不是可以把中间的过程省略呢?

在这里插入图片描述
我们着重要记住差分标记
在这里插入图片描述
我们根据上面的差分标记来试着操作一下
在这里插入图片描述
我们发现把标记后的差分数组,进行一次前缀和操作,可以得到最终的答案。
为什么会这样呢?
我们来看一下下图
在这里插入图片描述
这就是差分标记的由来。那么使用差分后时间复杂度是多少呢,为O(n+m)是一个线性的复杂度。

代码如下

#include<iostream>
using namespace std;int d[6] = { 0 };// 定义一个差分数组,长度为6(比原数组多1),并初始化为0。额外的1位是为了防止后续操作越界。// 实现对区间 [l, r] 进行加值操作
void add(int l, int r, int val)
{d[l] += val;     // 在位置 l 增加 val,表示从这个位置开始增加 vald[r + 1] -= val; // 在位置 r+1 减少 val,表示从 r+1 之后开始不再增加 val
}int main()
{// 定义初始数组 arr,内容为 {1, 3, 7, 5, 2}int arr[] = { 1,3,7,5,2 };// 对区间 [2, 4] 的元素增加 5add(2, 4, 5);// 对区间 [1, 3] 的元素增加 2add(1, 3, 2);// 对区间 [0, 2] 的元素减少 4add(0, 2, -4);// 遍历原数组,构建前缀和,将差分数组的变化累加到 d 数组中for (int i = 0; i < 5; i++){d[i] += d[i - 1]; // 将前一个位置的差分值累加到当前 d[i] 上,形成最终影响}// 将差分数组 d 的累加结果应用到原数组 arr 上,并输出修改后的数组for (int i = 0; i < 5; i++){arr[i] += d[i];    // 将差分值加到原数组上cout << arr[i] << " "; // 输出修改后的数组元素}// 将差分数组 d 置为 0,防止后续影响,但此处的 memset 用法有误,应为 sizeof(d) 而不是 sizeof(0)memset(d, 0, sizeof(d));return 0;
}

差分数组初始化0是没有任何影响的,不需要把d和sumd的数组求出来
在这里插入图片描述
gitee一维前缀和与一维差分源码


http://www.mrgr.cn/news/30605.html

相关文章:

  • 游戏引擎学习第五天
  • C#画图板代码
  • 【广西】《广西壮族自治区本级政务信息化建设和运维项目预算支出标准》(桂财建〔2023〕102号)-省市费用标准解读系列09
  • 计算机网络易混淆知识点串记
  • 解决C盘空间不足的三种方案
  • QtWebServer
  • Springboot请求响应案例
  • Deutsch intensiv C1 Schreiben
  • Maven 和 gradle JavaFX 项目的休眠行为差异
  • 2024java面试-软实力篇
  • VMware Workstation Pro 17下载及安装教程
  • 828华为云征文|华为Flexus云服务器打造 mediacms 线上影院
  • JS和Node.js的事件循环
  • 计算生物学:概念、历史、现状与展望?
  • iostat 命令:系统状态监控
  • 典型的MVC设计模式:使用JSP和JavaBean相结合的方式来动态生成网页内容典型的MVC设计模式
  • Springboot的三层架构
  • JDK自带的序列化
  • C++ : 继承问题 [virtual函数调用,为什么禁止在virtual使用默认参数]
  • 向上转移和向下转型
  • U盘显示未被格式化:深入解析、恢复策略与预防之道
  • 网络安全 DVWA通关指南 DVWA Stored Cross Site Scripting (存储型 XSS)
  • 蓝桥杯嵌入式客观题合集
  • 【字符函数】strcpy函数(字符串复制函数)+strcat函数(字符串追加)+strcmp函数(字符串比较)【笔记】
  • 英飞凌最新AURIX™TC4x芯片介绍
  • Lecture 4 Page Table