当前位置：首页 > news >正文

差分数组汇总

news 文章来源：https://blog.csdn.net/he_zhidan/article/details/139202741 2024/10/23 14:24:09

本文涉及知识点

算法与数据结构汇总

差分数组

令 a[i] = $\sum_{j:0}^{i}vDiff[i]$
如果 vDiff[i1]++，则a[i1…]全部++
如果vDiff[i2]–,则a[i2…]全部–。
令11 < i2 ，则：
$\begin{cases} a[i]不变，不受加减影响 && i < i1 \\ a[i]不变，加减抵消 && i >= i2\\ a[i]++ && other \\ \end{cases}$
即：a[i1…i2-1]++ ，其它不变。
区间更新、单点更新时间复杂度：O(1）。
区间查询、单点查询：O(n)
依次查询时间复杂度O(n)，i从0到n-1查询a[i]的总时间复杂度是O(n)。
可与树状数组结合：更新查询全部是O(logn)
空间复杂度：O(n)

题解

	难度分
【滑动窗口】【差分数组】C++算法：995K 连续位的最小翻转次数	1835
【区间合并差分数组】2963:统计好分割方案的数目	1984
【差分数组】2772. 使数组中的所有元素都等于零	2029
二分查找差分数组LeetCode2251:花期内花的数目	2022
【分解质因数差分数组】2584. 分割数组使乘积互质	2159
【差分数组】1674. 使数组互补的最少操作次数	2333
【前缀和二分查找差分数组】2528最大化城市的最小供电站数目	2235
【差分数组】【图论】【分类讨论】【整除以2】3017按距离统计房屋对数目	2709
【上下界分析差分数组】798得分最高的最小轮调

用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，省略。
即：
$\sum_{i:0}^{key}mDiff[i] \quad = \sum_{i:0}^{k}mDiff[i]$
如果x不为0，则[key,nkey)全部要开会。

二维差分

a[i][j] = $\sum_{i1:0}^i \sum_{j1:0}^jvDiff[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] = $\sum_{i1:0}^{i}vDiif[i1][j]$
a[i][j] = $\sum_{j1:0}^j vCol[j1]$

封装类

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;
};

题解

	难度分
【离散化二维差分】850. 矩形面积 II	2335
【二维差分】2132. 用邮票贴满网格图	2364
【离散化二维差分】391. 完美矩形

扩展阅读

视频课程

先学简单的课程，请移步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++**实现。