首页 > 其他分享 >一维差分/前缀和

一维差分/前缀和

时间:2024-02-28 22:00:29浏览次数:20  
标签:right 前缀 差分 一维 区间 operatorname left

算法笔记的第一篇文章

前缀和:

在做题时,我们经常会遇见这种问题:

给你一个长度为 \(n\) 的序列 \(a\),有 \(q\) 次询问,每次给出一个区间 \(\left[L, R\right]\), 请输出 \(a_l+a_{l + 1}+\cdots+a_r\) 的和。

对于这种问题,最为简单的方式莫过于 \(\operatorname{O}(nq)\) 暴力了。
但有没有更快的方法呢?

由于加法是可逆的,所以我们可以把区间 \(\left[L, R\right]\) 拆分成区间 \(\left[1, R\right]\) 减去区间 \(\left[1, L-1\right]\),所以我们可以预处理 \(a\) 的每一个前缀,达到 \(\operatorname{O}(1)\) 的查询。

预处理公式:

\[s_i =s_{i-1}+a_i \]

差分:

给你一个长度为 \(n\) 的序列 \(a\),有 \(q\) 次操作,每次给出一个区间 \(\left[L, R\right]\), 表示将 \(\left[L, R\right]\) 中的每一个数加 1, 让你输出 \(q\) 次操作后的数列。

对于这个问题,我们肯定能够想到 \(\operatorname{O}(nq)\) 的暴力写法。但可以用差分优化到 \(\operatorname{O}(n+q)\) 。

根据上述前缀和的公式我们不难发现,如果我们把 \(a_i\) 增加 1,那么 \(s_i,s_{i+1}\cdots s_n\) 都会增加 1。设差分数组为 \(d\), 那么我们把 \(d_L\) 加 1,把 \(d_R\) 减 1 即可。

但因为 \(\sum\limits_{j=1}^id_j\) 要等于 \(a_i\),根据前缀和公式,我们可以逆向求得 \(d_i= a_i-a_i-1\) 然后在 \(d\) 数组上操作就可以了。

标签:right,前缀,差分,一维,区间,operatorname,left
From: https://www.cnblogs.com/caoshurui/p/18042027

相关文章

  • 11 .Codeforces Round 891 (Div. 3)E. Power of Points(推公式+前缀和优化)
    E.PowerofPoints题解参考#include<bits/stdc++.h>#defineintlonglong#definerep(i,a,b)for(inti=(a);i<=(b);++i)#definefep(i,a,b)for(inti=(a);i>=(b);--i)#define_for(i,a,b)for(inti=(a);i<(b);++i)#definepii......
  • 差分和前缀和
    蓝桥杯第14届中的一道题所学:题目描述小蓝拥有n×n大小的棋盘,一开始棋盘上全都是白子。小蓝进行了m次操作,每次操作会将棋盘上某个范围内的所有棋子的颜色取反(也就是白色棋子变为黑色,黑色棋子变为白色)。请输出所有操作做完后棋盘上每个棋子的颜色。输入格式输入的第一行包......
  • day42 动态规划part4 代码随想录算法训练营 46. 携带研究材料- 一维数组写法
    题目:46.携带研究材料我的感悟:一维是二维的压缩理解难点:倒序遍历j因为每轮的数字是由左上决定的。遍历的时候,从右侧遍历,是不会影响左侧的。听课笔记:代码示例:defbag_problem(weight,value,bagWeight):#初始化dp=[0]*(bagWeight+1)fori......
  • 前缀和算法
    一、简析前缀和有一系列元素\(A[a_0,~a_1,~...,~a_n,~...]\),前缀和\(pre\_sum[n]=A[0]+A[1]+···+A[n]\)。利用前缀和,我们可以很高效地得到\([L,~R]\)的区间和\(\sum_{i=L}^{R}A[i]=pre\_sum[R]-pre\_sum[L-1]\)。二、相关问题2.1题目简述P8649[蓝桥杯2017省B]......
  • stm32单片机扫码设计方案,ESP32蓝牙无线扫码器设计项目硬件套件的实现,一维码二维码识别
    stm32/ESP32(或ESP32C3,ESP32S3)/ESP8266单片机扫码识别设计方案二维码一维码扫描模块开发项目资料程序,轻松实现蓝牙扫码器WiFi无线串口,二维码识别显示器串口输出条码扫描枪扫码枪开发项目套件设计,很适合DIY无需焊接,到手即可开发调试。ESP32,ESP8266等基于arduino库实现,stm32基于......
  • 差分约束
    解决形如$a_i\lex_i-y_i\leb_i$的不等式组,其中$a_i,b_i$是给定的常数。我们尝试连接边通过$\operatorname{spfa}$解决。连接以下两条边,跑最短路。$$\Large{x_i\overset{-a_i}{\to}y_i}$$$$\Large{y_i\overset{b_i}{\to}x_i}$$例题:[P7515](https://www.luogu.com.c......
  • 基于MCU的差分增量FOTA升级可用方案记录
    差分FOTA优点:占用空间小,非常适合用于lora,nbiot等慢速低数据量的升级用,相比全量升级的传输大小空间基本都有量级的节省。缺点:生产差分文件时需要基于上一版本,前后版本差异太大有的差分fota算法并不能很好的差分。难点:mcu一般flash空间和ram空间都很小,开源的大部分早期基本都是......
  • 【算法】007_前缀树和贪心算法
    1.前缀树一个字符串类型的数组arr1,另一个字符串类型的数组arr2.arr2中有哪些字符,是arr1中出现的?arr2中有哪些字符是作为arr1中某个字符串前缀出现的?arr2中有哪些字符是作为arr1中某个字符串前缀出现的?pass:表示当前这个结点被经过的次数end:这个结点作为结尾的次数例如......
  • 动态规划--一维dp和二维dp
    在解决背包问题时,使用一维动态规划数组和二维动态规划数组都是常见的方法,选择哪种方式取决于问题的特点和解法的需要。使用一维DP数组的情况:状态转移方程只涉及到上一行的元素:当状态转移方程只涉及到上一行的元素时,可以使用一维DP数组。这样能够降低空间复杂度,使算法更为简......
  • 一维动态规划题目
    746.使用最小花费爬楼梯力扣题目链接思路:暴力递归解题思路把每一种可能都枚举,也就是dfs搜索每一种可能的情况,再求出其中最小的花费返回即可。代码实现//求两个数中的最小值intmin(inta,intb){returna<b?a:b;}//表示从下标i开始到costSize-1位置的......