C++差分数组

前言

C++算法与数据结构
打开打包代码的方法兼述单元测试

差分数组（Difference Array）是一种巧妙的数据结构，常用于处理序列的各种动态修改问题，尤其是具有前后元素关联的操作。令数据数组是data,diff[i]记录data[i]-data[i-1]，则data[i] = diff[0…i]之和。差分数组的优点：常数时间进行区间修改。

引言

张三有a个桃，李四比张三多d1个桃，王五比李四多d2个桃… 求大家各有多少个桃。
令数组 diff = {a,d1,d2…}
数组a记录张三、李四、王五拥有的桃子数。则：
a[0] = diff[0]
a[1] = diff[0]+diff[1]
a[2] = diff[0] + diff[1] + diff[2]
即 a[i] = sum(diff[0…i]) ，即前缀和。
本题的diff就是差分数组。

典型应用

令共有n个顾客，张三的编号为0，李四的编号为1，王五的编号为2…
经过m次操作（编号i1到i2都顾客都给予x个桃)后，求各顾客拥有的桃子数。
每次操作，区间修改差分数组，时间复杂度：O(1)。m次操作时间复杂度O(m)。
操作结束后，统一计算前缀和，时间复杂度O(n)。
解题时间复杂度：O(n+m)，暴力解题的时间复杂度是:O(nm)

差分数组

令 a[i] = ∑ j : 0 i v D i f f [ i ] \sum_{j:0}^{i}vDiff[i] ∑j:0i​vDiff[i]
如果 vDiff[i1]++，则a[i1…]全部++
如果vDiff[i2]–,则a[i2…]全部–。
令11 < i2 ，则：
{ a [ i ] 不变，不受加减影响 i < i 1 a [ i ] 不变，加减抵消 i > = i 2 a [ i ] + + o t h e r \begin{cases} a[i]不变，不受加减影响 && i < i1 \\ a[i]不变，加减抵消 && i >= i2\\ a[i]++ && other \\ \end{cases} ⎩ ⎨ ⎧​a[i]不变，不受加减影响a[i]不变，加减抵消a[i]++​​i<i1i>=i2other​
即：a[i1…i2-1]++ ，其它不变。
区间更新、单点更新时间复杂度：O(1）。
区间查询、单点查询：O(n)
依次查询时间复杂度O(n)，i从0到n-1查询a[i]的总时间复杂度是O(n)。
可与树状数组结合：更新查询全部是O(logn)
空间复杂度：O(n)
为了处理边界情况，vDiff往往比a多一个元素，方便处理最后一个元素+1。vDiff[n-1]++ vDiff[n]–。

题解

部分文章已完成，将陆续发布，估计2024年10月11号之前发布完毕。

用map实现的差分

封装类

template<class KEY=int,class VALUE=int>class CMapDiff{public:void Set(KEY left, KEY rExclue, VALUE value) {m_mDiff[left]+= value;m_mDiff[rExclue]-= value;}vector<pair<KEY, VALUE>> Ans()const {vector<pair<KEY, VALUE>> res;VALUE sum = 0;for (const auto& [key,value]: m_mDiff) {sum += value;res.emplace_back(make_pair(key, sum));}return res;}protected:map<KEY, VALUE> m_mDiff;};

【区间合并 差分 栈】3169. 无需开会的工作日
大约2024年7月3号发

mDiff[si]++ mDiff[ei+1]-- 表示[si,ei] 一场会议。
∀ \forall ∀mDiff的键 key,其下一个键为nkey。
则 ∀ \forall ∀k ∈ \in ∈ [key,nkey) mDiff[k]都为0，省略。
即：
x = ∑ i : 0 k e y m D i f f [ i ] = ∑ i : 0 k m D i f f [ i ] x = \sum_{i:0}^{key}mDiff[i] \quad = \sum_{i:0}^{k}mDiff[i] x=∑i:0key​mDiff[i]=∑i:0k​mDiff[i]
如果x不为0，则[key,nkey)全部要开会。

二维差分

a[i][j] = ∑ i 1 : 0 i ∑ j 1 : 0 j v D i f f [ i ] [ j ] \sum_{i1:0}^i \sum_{j1:0}^jvDiff[i][j] ∑i1:0i​∑j1:0j​vDiff[i][j] 即以(0,0)为左上角，(i,j)为右下角的长方形之和。
a[i1…i2][j1…j2] ++的操作：
vDiff[i1][j1]++ vDiff[i2+1][j2+1]++
vDiif[i1][j2+1]-- vDiff[2+1][j1]–
注意：差分都是左闭右开空间
求前缀和的简单方法：
vCol[j] = ∑ i 1 : 0 i v D i i f [ i 1 ] [ j ] \sum_{i1:0}^{i}vDiif[i1][j] ∑i1:0i​vDiif[i1][j]
a[i][j] = ∑ j 1 : 0 j v C o l [ j 1 ] \sum_{j1:0}^j vCol[j1] ∑j1:0j​vCol[j1]

以(0,0)为左上角，(r,c)为右下角的长方形之和，分以下五种情况：
一， 包括(r2+1,c2+1)的长方形,和为1-1+1-1=0，上图绿色显示。
二， 排除情况一，包括(r1,c2+1)的长方形，必定包括(r,c)，且不包括其它点，其和为1-1=0。上图蓝色显示。
三， 包括(r2+1,c1)的长方形和情况二类似。
四， 不包括四个单格的矩形，其和为0。上图红色显示。
五， 余下的单格，只包括(r1,c1)，和为1。刚好是(r1,c1)为左上角，(r2,c2)位为右下角的长方形。

封装类

template<class T = int >class CDiff2{public:CDiff2(int r, int c):m_iR(r),m_iC(c) {m_vDiff.assign(m_iR, vector<T>(m_iC));}void Set(int r1, int c1, int r2Exinc, int c2Exinc,int iAdd) {m_vDiff[r1][c1] += iAdd;m_vDiff[r2Exinc][c2Exinc] += iAdd;m_vDiff[r1][c2Exinc] -= iAdd;m_vDiff[r2Exinc][c1] -= iAdd;}vector<vector<T>> Ans()const {vector<vector<T>> res(m_iR, vector<T>(m_iC));vector<T> vCols(m_iC);for (int r = 0; r < m_iR; r++) {T iSum = 0;for (int c = 0; c < m_iC; c++) {vCols[c] += m_vDiff[r][c];iSum += vCols[c];res[r][c] = iSum;}}return res;}const int m_iR, m_iC;protected:vector<vector<T>> m_vDiff;};

题解

数组数组实现差分

区间修改：O(logn)
查询：O(logn)

扩展阅读

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关推荐

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。