2022.3.1#差分与前缀和思想

本文主要是介绍2022.3.1#差分与前缀和思想，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

差分：

给出n个数，再给出Q个询问，每个询问给出l，r，x，要求你在l到r上每一个值都加上x，而只给你O(n)的时间范围，怎么办？

Xenny大佬的树状数组详解 - Xenny - 博客园 (cnblogs.com)里利用一个差分值构建的树状数组，可以用来进行区间更新，单点查询。

差分的特点是区间[a,b]加k的话，我只要对差分数组的d[a]+k,d[b+1]-k即可（注意如果b+1>n则d[b+1]不变）

“则有 A[i] = Σⁱ_{j = 1}D[j];(D[j] = A[j] - A[j-1])，即前面i项的差值和，这个有什么用呢？例如对于下面这个数组

• A[] = 1 2 3 5 6 9
• D[] = 1 1 1 2 1 3

如果我们把[2,5]区间内值加上2，则变成了

• A[] = 1 4 5 7 8 9
• D[] = 1 3 1 2 1 1

发现了没有，当某个区间[x,y]值改变了，区间内的差值是不变的，只有D[x]和D[y+1]的值发生改变，至于为什么我想我就不用解释了吧。”（转自Xenny）

单点查询上，可以知道A[i]=D[1]+D[2]+....+D[i-1]+D[i]，会使得单点十分好求。

这是线性的差分。

 前缀和可以看作给你一个差分数组，你要建立一个原数组。

这篇关于2022.3.1#差分与前缀和思想的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！