前缀和差分【算法 13】

2024-08-31 04:36
文章标签 算法 13 前缀 差分

本文主要是介绍前缀和差分【算法 13】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

在算法领域中,前缀和与差分数组是两种高效处理区间问题的技术。它们能在特定问题场景下将时间复杂度从 (O(n)) 降到 (O(1)),适用于频繁的区间查询与修改操作。本文将简要介绍这两种技术及其应用。
请添加图片描述

1. 前缀和 (Prefix Sum)

前缀和是指一个数组的第 (i) 个前缀和为原数组前 (i) 个元素之和。通过构建前缀和数组,我们可以高效地进行区间求和。

前缀和公式:

设原数组为 (A),前缀和数组为 (P),那么:
P [ i ] = A [ 1 ] + A [ 2 ] + . . . + A [ i ] P[i] = A[1] + A[2] + ... + A[i] P[i]=A[1]+A[2]+...+A[i]
利用前缀和,可以快速计算任意区间 ([l, r]) 的和:
sum ( l , r ) = P [ r ] − P [ l − 1 ] \text{sum}(l, r) = P[r] - P[l-1] sum(l,r)=P[r]P[l1]

这种方法将单次区间求和的时间复杂度从 (O(n)) 降到 (O(1)),而构建前缀和数组的时间复杂度为 (O(n))。

示例代码:
void buildPrefixSum(int A[], int P[], int n) {P[0] = A[0];for (int i = 1; i < n; i++) {P[i] = P[i-1] + A[i];}
}int querySum(int P[], int l, int r) {return l == 0 ? P[r] : P[r] - P[l-1];
}
应用场景:
  • 频繁的区间和查询,例如在区间内求和、计算连续子数组的和等。

2. 差分数组 (Difference Array)

差分数组是一种高效处理区间修改的工具。差分数组的核心思想是记录变化,而不是直接修改原数组。通过构造一个差分数组,可以在 (O(1)) 时间内对原数组的一个区间进行增量更新。

差分数组公式:

设原数组为 (A),差分数组为 (D),那么:
D [ i ] = A [ i ] − A [ i − 1 ] D[i] = A[i] - A[i-1] D[i]=A[i]A[i1]

通过差分数组,我们可以对区间 ([l, r]) 进行增量修改,假设增加值为 (x),则:
D [ l ] + = x D[l] += x D[l]+=x

D [ r + 1 ] − = x D[r+1] -= x D[r+1]=x

最后,通过构建最终的数组,我们可以恢复修改后的原数组。

示例代码:
void buildDifferenceArray(int A[], int D[], int n) {D[0] = A[0];for (int i = 1; i < n; i++) {D[i] = A[i] - A[i-1];}
}void updateRange(int D[], int l, int r, int x) {D[l] += x;if (r + 1 < n) {D[r + 1] -= x;}
}void applyDifferenceArray(int A[], int D[], int n) {A[0] = D[0];for (int i = 1; i < n; i++) {A[i] = A[i-1] + D[i];}
}
应用场景:
  • 大量的区间修改操作,例如在区间内对所有元素增加一个固定值、或区间内累加值的变化。

3. 综合运用

在实际问题中,前缀和与差分数组可以结合使用。例如,差分数组用于快速区间修改,前缀和用于快速区间查询。两者的结合可以高效解决大量的区间操作问题。

总结

  • 前缀和 适合频繁的区间查询,其核心在于通过预处理将区间求和问题简化为常数时间查询。
  • 差分数组 适合频繁的区间修改,其核心在于记录变化,而不是直接修改原数组。

通过灵活使用这两种工具,我们可以高效地处理许多涉及区间的算法问题。

这篇关于前缀和差分【算法 13】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1122904

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

Java进阶13讲__第12讲_1/2

多线程、线程池 1.  线程概念 1.1  什么是线程 1.2  线程的好处 2.   创建线程的三种方式 注意事项 2.1  继承Thread类 2.1.1 认识  2.1.2  编码实现  package cn.hdc.oop10.Thread;import org.slf4j.Logger;import org.slf4j.LoggerFactory

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

秋招最新大模型算法面试,熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候,不知道面试完会不会复盘、总结,做笔记的习惯,这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助,都附有完整答案,熬夜也要看完,祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN,还有完整版的大模型 AI 学习资料,朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费

poj 3159 (spfa差分约束最短路) poj 1201

poj 3159: 题意: 每次给出b比a多不多于c个糖果,求n最多比1多多少个糖果。 解析: 差分约束。 这个博客讲差分约束讲的比较好: http://www.cnblogs.com/void/archive/2011/08/26/2153928.html 套个spfa。 代码: #include <iostream>#include <cstdio>#i

poj 3169 spfa 差分约束

题意: 给n只牛,这些牛有些关系。 ml个关系:fr 与 to 牛间的距离要小于等于 cost。 md个关系:fr 与 to 牛间的距离要大于等于 cost。 隐含关系: d[ i ] <= d[ i + 1 ] 解析: 用以上关系建图,求1-n间最短路即可。 新学了一种建图的方法。。。。。。 代码: #include <iostream>#include