一维差分、二维差分模板

本文主要是介绍一维差分、二维差分模板，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一维差分

参考资料：

【C++】一维、二维差分+模板+例题_c语言差分练习题-CSDN博客

模板题目：

https://www.luogu.com.cn/problem/P2367

模板代码：

#include <stdint.h>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <thread>
#include <iostream>using namespace std;const int maxn = 5e6+5;
int a[maxn];
int diff[maxn];void insert(int l, int r, int c)
{diff[l] += c;diff[r+1] -= c;
}int main() {int n,p;cin >> n >> p;for(int i=1;i<=n;++i){cin >> a[i];}a[0]=0;for(int i=1;i<=n;++i){diff[i] = a[i] - a[i-1];}int l,r,c;while(p--){cin >> l >> r >> c;insert(l, r, c);}int ans = maxn, sum =0;for(int i=1;i<=n;++i){sum+=diff[i];ans = min(ans, sum);}cout << ans <<endl;// system("pause");return 0;
}

二维差分

参考资料：

算法基础（五）| 差分算法及模板详解-腾讯云开发者社区-腾讯云

差分——（2）二维差分_二维差分非矩形-CSDN博客

算法笔记（六）：差分法_差分算法-CSDN博客

模板题目：

https://www.luogu.com.cn/problem/P5542

模板代码：

这篇关于一维差分、二维差分模板的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---