【模板】差分

原创于 2024-04-16 12:01:11 发布 · 粉丝可见 · 575 阅读 · 5 · 4 · 本内容遵循CC 4.0 BY-SA版权协议版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 GEO检测 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/137819090

本题链接：登录—专业IT笔试面试备考平台_牛客网

题目：

样例：

`cobol<br/>3 2<br/>1 2 3<br/>1 2 4<br/>3 3 -2<br/>`

5 6 1

思路：

一直以来，我总是不太理解差分和树状数组操作区别。

现在摸了一下开始有所理解了。

差分和树状数组的区别：

树状数组：可以边区间插入操作边查询。

差分：一系列区间操作后，最后确定结果序列

差分原理：

设
原数组为 a
差分数组为 b
前缀和数组为 c

这里要注意的是，操作差分的时候，+x 前后的关系
差分就是 差分数组的前缀和 = 原数组相应位置的前缀和
例如：
b1 = a1 - 0
b2 = a2 - a1
b3 = a3 - a2

1
2
3

b1 + b2 + b3 = c3
 
c3 = a1 + a2 + a3

所以相应关系后，操作差分数组函数如下，理解相应核心内容：

初始时添加数值序列：

for(int i = 1,x;i <= n;++i)
{
    cin >> x;
    Insert(i,i,x);
}

区间添加修改函数：

inline void Insert(int l, int r, int x)
{
    a[l] += x;          // 前缀和 a[l] += x;
    a[r + 1] -= x;      // 区间 a[r] 因为前面 +x 了，所以要维持差分前缀和不变，所以 r+1 -= x
}

获取最终操作结果序列函数：

inline void getArray()
{
    for (int i = 1; i <= n; ++i)        // 最后求 差分的前缀和
    {
        a[i] += a[i - 1];               // 差分的前缀和，就是相应原数组操作后的前缀和
    }
}

代码详解如下：

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#define endl '\n'
#define int long long
#define YES puts("YES")
#define NO puts("NO")
#define umap unordered_map
#define All(x) x.begin(),x.end()
#pragma GCC optimize(3,"Ofast","inline")
#define IOS std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 2e6 + 10;
inline void solve();
 
signed main()
{
//	freopen("a.txt", "r", stdin);
	IOS;
	int _t = 1;
//	cin >> _t;
	while (_t--)
	{
		solve();
	}
	return 0;
}
int n,q,a[N];
 
inline void Insert(int l,int r,int x)
{
	a[l] += x;
	a[r + 1] -= x;
}
inline void getArray()
{
	for(int i = 1;i <= n;++i)
	{
		a[i] += a[i - 1];
	}
}
inline void solve()
{
	cin >> n >> q;
	for(int i = 1,x;i <= n;++i)
	{
		cin >> x;
		Insert(i,i,x);	// 初始插入序列
	}
	while(q--)
	{
		int l,r,x;
		cin >> l >> r >> x;
		Insert(l,r,x);	// 区间修改
	}
	getArray();	// 获取最后系列操作后结果序列
	for(int i = 1;i <= n;++i) cout << a[i] << ' ';
}