本题链接：登录—专业IT笔试面试备考平台_牛客网
题目：
样例：
|
| 5 6 1 |
思路：
一直以来，我总是不太理解差分和树状数组操作区别。
现在摸了一下开始有所理解了。
差分和树状数组的区别：
树状数组：可以边区间插入操作边查询。
差分：一系列区间操作后，最后确定结果序列
差分原理：
设
原数组为 a
差分数组为 b
前缀和数组为 c
这里要注意的是，操作差分的时候，+x 前后的关系
差分 就是 差分数组的前缀和 = 原数组相应位置的前缀和
例如：
b1 = a1 - 0
b2 = a2 - a1
b3 = a3 - a2
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] << ' ';
}
