差分和前缀和的原理、用法和区别。

前缀和(Prefix Sum)

核心思想:预处理数组的前缀和,快速回答「区间和查询」
适用场景:数组静态(更新少、查询多),需要频繁计算任意区间的和

1. 定义与构建

对于原数组  a[0...n-1] ,前缀和数组  preSum  满足:
preSum[i] = a[0] + a[1] + ... + a[i-1] 
( preSum[0] = 0 ,方便边界计算)

构建代码:

vector<long long> buildPreSum(vector<int>& a) {
int n = a.size();
vector<long long> preSum(n + 1, 0);
for (int i = 0; i < n; ++i) {
preSum[i + 1] = preSum[i] + a[i];
}
return preSum;
}

2. 核心作用:O(1) 区间和查询

原数组区间  [l, r] (闭区间)的和为:
sum(l, r) = preSum[r + 1] - preSum[l] 

示例:
原数组  a = [1, 2, 3, 4] ,则  preSum = [0, 1, 3, 6, 10] 
查询  a[1..3] (元素  2,3,4 )的和: preSum[4] - preSum[1] = 10 - 1 = 9 

差分(Difference Array)

核心思想:预处理差分数组,快速执行「区间更新」
适用场景:数组动态(更新多、查询少),需要频繁对区间进行加减操作

1. 定义与构建对于原数组  

a[0...n-1] ,差分数组  diff  满足:
diff[i] = \begin{cases} 
a[0] & (i=0) \\
a[i] - a[i-1] & (i>0) 
\end{cases} 

构建代码(直接初始化,或从原数组推导):

vector<int> buildDiff(vector<int>& a) {
int n = a.size();
vector<int> diff(n, 0);
diff[0] = a[0];
for (int i = 1; i < n; ++i) {
diff[i] = a[i] - a[i-1];
}
return diff;
}

2. 核心操作:O(1) 区间更新

对原数组  a  的区间  [l, r]  全部加  val ,只需操作差分数组:

diff[l] += val;           // 起点 l 开始有增量
if (r + 1 < n) {
diff[r + 1] -= val;   // 终点 r+1 处取消增量(防止扩散到区间外)
}


原理:差分数组记录的是「相邻元素的变化量」。当通过前缀和还原原数组时, diff[l] += val  的影响会传递到  a[l..n-1] ,而  diff[r+1] -= val  会抵消  r+1  之后的影响,最终只有  a[l..r]  被加上  val 。

3. 还原原数组(从差分 → 原数组)

对差分数组求前缀和,即可还原原数组:

vector<int> restoreArray(vector<int>& diff) {
int n = diff.size();
vector<int> a(n, 0);
a[0] = diff[0];
for (int i = 1; i < n; ++i) {
a[i] = a[i-1] + diff[i];
}
return a;
}

或更高效的原地操作(差分数组直接变原数组):

for (int i = 1; i < n; ++i) {
diff[i] += diff[i-1];
}
// 此时 diff 数组等价于原数组 a

前缀和 vs 差分:核心区别 

特性 前缀和(Prefix Sum) 差分(Difference Array) 
核心用途 快速查询区间和(静态数组) 快速执行区间更新(动态数组) 
操作对象 原数组 → 前缀和数组(预处理) 原数组 → 差分数组(预处理) 
时间复杂度 构建 O(n),查询 O(1) 构建 O(n),区间更新 O(1),还原 O(n) 
典型场景 数组不变,频繁查区间和(如 LeetCode 560) 数组常变,频繁对区间加减(如 LeetCode 1109) 

综合示例:前缀和 + 差分

题目:

1. 初始数组  a = [1, 2, 3, 4] 
2. 对区间  [1, 3] (元素  2,3,4 )加  5 
3. 查询最终数组的区间  [0, 2] (元素  1,7,8 )的和

步骤 1:用差分执行区间更新

原数组  a = [1, 2, 3, 4] ,构建差分数组:

diff = [1, 1, 1, 1]  // 因为 2-1=1, 3-2=1, 4-3=1


对区间  [1, 3]  加  5 :

diff[1] += 5;   // diff[1] = 6
if (3+1 < 4) diff[4] -=5;  // 数组长度 4,r+1=4 越界,无需操作


此时差分数组  diff = [1, 6, 1, 1] 

步骤 2:还原原数组(差分 → 原数组)

对  diff  求前缀和:

a[0] = 1  
a[1] = 1 + 6 = 7  
a[2] = 7 + 1 = 8  
a[3] = 8 + 1 = 9  


还原后数组  a = [1, 7, 8, 9] 

步骤 3:用前缀和查询区间和

构建前缀和数组  preSum :

preSum = [0, 1, 8, 16, 25]  


查询区间  [0, 2]  的和:

sum = preSum[3] - preSum[0] = 16 - 0 = 16

总结

- 前缀和是「区间和查询」的优化工具,适合数组静态、查询频繁的场景。
- 差分是「区间更新」的优化工具,适合数组动态、更新频繁的场景。
- 两者常配合使用:用差分处理更新,再用前缀和处理查询,覆盖更复杂的需求。

理解这两个技巧的核心逻辑后,很多数组操作的题目(尤其是竞赛题)都能迎刃而解。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.pswp.cn/pingmian/88228.shtml
繁体地址,请注明出处:http://hk.pswp.cn/pingmian/88228.shtml
英文地址,请注明出处:http://en.pswp.cn/pingmian/88228.shtml

如若内容造成侵权/违法违规/事实不符,请联系英文站点网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

C++并发编程-12. 用内存顺序实现内存模型

前情回顾 前文我们介绍了六种内存顺序&#xff0c;以及三种内存模型&#xff0c;本文通过代码示例讲解六种内存顺序使用方法&#xff0c;并实现相应的内存模型。全局一致性模型同步模型(获取和释放)松散模型memory_order_seq_cst memory_order_seq_cst代表全局一致性顺序&#…

AI测试革命:从智能缺陷检测到自愈式测试框架的工业实践

AI测试革命&#xff1a;从智能缺陷检测到自愈式测试框架的工业实践 希望对大家有用&#xff01; 目录AI测试革命&#xff1a;从智能缺陷检测到自愈式测试框架的工业实践希望对大家有用&#xff01;一、传统测试之殇&#xff1a;工业质检的切肤之痛二、智能缺陷检测系统架构1. …

二、深度学习——损失函数

二、损失函数损失函数定义&#xff1a;损失函数是用来衡量模型参数的质量的函数&#xff0c;衡量方式是比较网络输出和真实输出的差异别名&#xff1a;损失函数&#xff08;loss function&#xff09;&#xff0c;代价函数&#xff08;cost function&#xff09;&#xff0c;目…

面向数据报的套接字通道技术详解

数据报通道基础 通道特性与创建方式 java.nio.channels.DatagramChannel类实例代表数据报通道&#xff0c;默认处于阻塞模式。通过configureBlocking(false)方法可将其配置为非阻塞模式。创建数据报通道需调用其静态open()方法&#xff0c;若用于IP组播则需指定组播组的地址类型…

147.在 Vue3 中使用 OpenLayers 地图上 ECharts 模拟飞机循环飞行

&#x1f9e9; 效果预览 &#x1f447; 飞机从多个城市起飞并向其他城市飞行&#xff0c;动画流畅&#xff0c;地图可缩放拖拽&#xff1a; &#x1f4e6; 一、项目技术栈 技术用途Vue 3现代前端框架OpenLayers地图底图渲染ECharts ol-echarts飞机飞行动画渲染ol-echarts将 …

OCR与PDF解析的区别

我们日常所接触的文档中&#xff0c;经常能碰到多语言混合的文档。比如论文试卷、财报研报、跨国票据都含有多种语言和文字。要将文档中的内容识别并提取务必需要使用到OCR技术&#xff0c;而传统的OCR工具在处理这类型文档的时候有局限性。早期的 OCR 系统识别精度有限&#x…

Java 单例类详解:从基础到高级,掌握线程安全与高效设计

作为一名Java开发工程师&#xff0c;你一定对**单例模式&#xff08;Singleton Pattern&#xff09;**不陌生。它是23种经典设计模式中最简单也是最常用的一种&#xff0c;用于确保一个类在整个应用程序中只有一个实例存在。单例广泛应用于系统配置、数据库连接池、日志管理器、…

面向对象设计

你列出的这些属于 C 高级开发中面向对象设计与架构设计的核心知识&#xff0c;也是面试高级工程师岗位必问的内容。下面我按顺序&#xff0c;深入讲解每一项概念、原理、用途&#xff0c;并穿插 C 示例。✅ 1. 设计原则&#xff08;SOLID&#xff09;SOLID 是面向对象设计的五大…

IntelliJ IDEA让我的开发效率翻倍:从新手到高效开发者的进阶之路

IntelliJ IDEA让我的开发效率翻倍&#xff1a;从新手到高效开发者的进阶之路 &#x1f31f; 嗨&#xff0c;我是IRpickstars&#xff01; &#x1f30c; 总有一行代码&#xff0c;能点亮万千星辰。 &#x1f50d; 在技术的宇宙中&#xff0c;我愿做永不停歇的探索者。 ✨ 用…

css sprites使用

CSS Sprites 是一种将多个小图标或背景图像合并到一个大图中的技术。通过减少HTTP请求次数&#xff0c;可以显著提高页面加载速度。其核心原理是&#xff1a;通过设置元素的背景图&#xff08;background-image&#xff09;为这个大图&#xff0c;然后调整背景位置&#xff08;…

分布式爬虫在电商平台商品数据大规模采集中的技术应用

在电商平台商品数据大规模采集场景中&#xff0c;分布式爬虫凭借其高效、可扩展、抗风险的特性&#xff0c;成为突破单节点爬虫性能瓶颈的核心技术方案。以下从技术架构、关键技术点、电商场景适配及挑战应对四个维度&#xff0c;解析其具体应用&#xff1a;一、分布式爬虫的核…

Linux的`if test`和`if [ ]中括号`的取反语法比较 笔记250709

Linux的if test和if 中括号的取反语法比较 笔记250709 Linux的 test命令&#xff08;或等价中括号写法 [空格expression空格]&#xff09;的用法详解. 笔记250709 四种取反语法: if ! test -e xxx ;then... 和 if test ! -e xxx ;then... 和 if ! [ -e xxx ] ;then... 和 if …

记录使用ubuntu16.04编译aosp(android8.1与10)遇到的问题

一、前言&#xff1a; 本来打算用wsl来编译AOSP&#xff0c;但是折腾了好几天&#xff0c;以失败告终。后来使用vmware反而成功了。 本篇同样会把wsl遇到的问题与尝试记录下来。 环境&#xff1a;vmware ubuntu16.04。 为什么会使用ubuntu16.04呢&#xff0c;因为在公司有一…

hiredis window之RFDMap

简介 RFDMap用于将socket分配映射成连续的文件描述符&#xff0c;同时管理回收的文件描述符&#xff0c;因为ae构架中管理fd与对应事件处理器使用的是数据&#xff0c;fd作为数组下标 结构 #mermaid-svg-zQz2LTrKRi0LQTII {font-family:"trebuchet ms",verdana,arial…

RustFS一款Rust 驱动的 高性能 分布式存储系统

演示地址&#xff1a;https://play.rustfs.com/browser 访问账号&#xff08;默认 rustfsadmin&#xff09;。 访问密钥&#xff08;默认 rustfsadmin&#xff09;。 下载mc https://dl.min.io/client/mc/release可以直接在 Linux 系统上安装 mc&#xff08;&#xff0c;然后访…

微软 Bluetooth LE Explorer 实用工具的详细使用分析

微软 Bluetooth LE Explorer 实用工具的详细使用分析 文章目录 微软 **Bluetooth LE Explorer** 实用工具的详细使用分析1. **工具定位与核心功能**2. **关键特性与更新**3. **使用场景示例**4. **系统要求与依赖**5. **与专业工具对比**6. **局限性**7. **实践建议**结论以下是…

centos 7.6安装mysql8

在 CentOS 7.6 上安装 MySQL 8.0.42 的步骤如下&#xff0c;基于搜索结果中的最新信息&#xff1a; 下载 MySQL 8.0.42 安装包 https://dev.mysql.com/downloads/mysql/从 MySQL 官方网站下载 mysql-8.0.42-1.el7.x86_64.rpm-bundle.tar 文件&#xff1a; 官方下载地址&#xf…

CentOS7更换阿里云yum源

问题&#xff1a;刚刚在本地安装了CentOS7虚拟机&#xff0c;使用yum安装vim软件时&#xff08;最小化安装只有vi没有vim&#xff09;出现下面的报错原因 &#xff1a;CentOS7 已于2024-6-30停止维护&#xff0c;官方镜像源已不可用&#xff0c;可以更换为阿里云镜像源解决&…

UE5内置插件 AnimToTexture 简单入门

开启插件 首先安装插件&#xff0c;然后重启。打开显示插件内容我们就可以找到插件自带的转换内容将骨骼网格体转换为顶点动画有两种方式&#xff1a; 最简单的记录每个顶点的位置然后通过切换拾取颜色偏移实现记录骨骼的变换&#xff0c;然后通过贴图去修改骨骼位置计算 这两种…

如何搭建Appium环境?

&#x1f345; 点击文末小卡片&#xff0c;免费获取软件测试全套资料&#xff0c;资料在手&#xff0c;涨薪更快1、安装Java Development Kit&#xff08;JDK&#xff09;前往Oracle官网下载JDK。在https://www.oracle.com/java/technologies/javase-jdk11-downloads.html 找到…