差分思想（精辟）

忘是亡心i 2022-03-15 15:26 266阅读 0赞

首先介绍差分思想：

设数组a\[\]=\{1,6,8,5,10\}，那么差分数组b\[\]=\{1,5,2,-3,5\}

也就是说b\[i\]=a\[i\]-a\[i-1\];(a\[0\]=0;)，那么a\[i\]=b\[1\]+....+b\[i\];(这个很好证的)。

当要改变区间\[ 2, 4 \]的时候，对于b数组来说，只要改变 b\[ x \] 和 b\[ 2+1 \]

所以对区间\[x,y\]进行修改,只用修改b\[x\]与b\[y+1\]:

b\[x\]=b\[x\]+k;b\[y+1\]=b\[y+1\]-k;

来看题目：

## 题目描述 ##

如题，已知一个数列，你需要进行下面两种操作：

1.将某区间每一个数数加上x

2.求出某一个数的值

## 输入输出格式 ##

**输入格式：**

第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。

第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。

接下来M行每行包含2或4个整数，表示一个操作，具体如下：

操作1： 格式：1 x y k 含义：将区间\[x,y\]内每个数加上k

操作2： 格式：2 x 含义：输出第x个数的值

**输出格式：**

输出包含若干行整数，即为所有操作2的结果。

## 输入输出样例 ##

**输入样例\#1：** 复制

5 5
    1 5 4 2 3
    1 2 4 2
    2 3
    1 1 5 -1
    1 3 5 7
    2 4

**输出样例\#1：** 复制

6
    10

运用差分和树状数组（树状数组可以维护前缀和）,当遇到区间操作的时候，运用差分思想，然后输出某个数的和的时候，就用差分的树状数组和

上代码

题目描述
    如题，已知一个数列，你需要进行下面两种操作：
    
    1.将某区间每一个数数加上x
    
    2.求出某一个数的值
    
    输入输出格式
    输入格式：
    第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。
    
    第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。
    
    接下来M行每行包含2或4个整数，表示一个操作，具体如下：
    
    操作1： 格式：1 x y k 含义：将区间[x,y]内每个数加上k
    
    操作2： 格式：2 x 含义：输出第x个数的值
    
    输出格式：
    输出包含若干行整数，即为所有操作2的结果。
    
    输入输出样例
    输入样例#1： 
    5 5
    1 5 4 2 3
    1 2 4 2
    2 3
    1 1 5 -1
    1 3 5 7
    2 4
    输出样例#1： 
    6
    10

发表评论取消回复

表情：

评论列表（有 0 条评论，266人围观）

还没有评论，来说两句吧...

相关阅读

相关【算法| 差分 No.1】AcWing 797. 差分 & AcWing 798. 差分矩阵

【算法| 差分 No.1】AcWing 797. 差分 & AcWing 798. 差分矩阵

墨蓝/ 2024年04月27日 06:57/ 0 赞/ 74 阅读

相关前缀和与差分 AcWing 798. 差分矩阵

前缀和与差分 AcWing 798. 差分矩阵原题链接 [AcWing 798. 差分矩阵][AcWing 798.] 算法标签差分思路 ![

淩亂°似流年/ 2023年09月28日 11:16/ 0 赞/ 43 阅读

相关牛人精辟辨析单端信号和差分信号

牛人精辟辨析单端信号和差分信号 21ic电子网昨天单端信号单端信号是相对于差分信号而言的，单端输入指信号有一个参考端和一个信号端构成，参考端一般为地端。

男娘i/ 2022年11月10日 01:21/ 0 赞/ 130 阅读

相关一阶差分与二阶差分及还原

一阶差分与二阶差分及还原一阶差分 arr = np.arange(10) np.random.shuffle(arr) arr = pd.

比眉伴天荒/ 2022年10月06日 11:53/ 0 赞/ 611 阅读

相关 732 我的日程安排表 III（差分思想）

1. 问题描述：当 k 个日程安排有一些时间上的交叉时（例如 k 个日程安排都在同一时间内），就会产生 k 次预订。给你一些日程安排 \[start, end) ，请你在每

偏执的太偏执、/ 2022年09月10日 04:24/ 0 赞/ 134 阅读

相关差分差分差分

class Solution { public: / 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可返回m天后

我不是女神ヾ/ 2022年08月31日 02:15/ 0 赞/ 285 阅读

相关差分思想（精辟）

首先介绍差分思想：设数组a\[\]=\{1,6,8,5,10\}，那么差分数组b\[\]=\{1,5,2,-3,5\} 也就是说b\[i\]=a\[i\]-a\[i-1\

忘是亡心i/ 2022年03月15日 15:26/ 0 赞/ 267 阅读

相关【2019.7.10】树上差分杂[LCA 倍增][树上差分点差分边差分]

多用于记录树上节点被经过的次数,记录某条边被经过的次数的时候点差分 [P3128 \[USACO15DEC\]最大流Max Flow][P3128_ _US

迷南。/ 2021年11月17日 15:44/ 0 赞/ 339 阅读

相关差分

概念对于一个数组a\[n\]，有m次操作，都是对区间\[l,r\]加上k，完事后输出数组在知道第一个数a\[1\]的情况下，如果我们知道后面的数与前一个数的差值p，

我不是女神ヾ/ 2021年11月01日 10:04/ 0 赞/ 372 阅读

相关思想的沉淀,精辟,杨澜如是说

1.男人的帅不在脸蛋，而在岁月积淀下来的睿智与淡定。 2.辛辛苦苦，过舒服日子；舒舒服服，过辛苦日子。 3.婚姻需要爱情之外的另一种纽带，最强韧的一种不是孩子，不是金钱

本是古典何须时尚/ 2021年10月19日 10:58/ 0 赞/ 264 阅读