差分题练习（区间更新）

走在努力路上的自己

发布于 2024-03-04 09:24:55

660

发布于 2024-03-04 09:24:55

文章被收录于专栏：走在努力路上的自己走在努力路上的自己

一、差分的特点和原理

对于一个数组a[]，差分数组diff[]的定义是:

对差分数组做前缀和可以还原为原数组:

利用差分数组可以实现快速的区间修改，下面是将区间[l, r]都加上x的方法:

diff[l] += x;
diff[r + 1] -= x;

在修改完成后，需要做前缀和恢复为原数组，所以上面这段代码的含义是:

diff[l]+=x表示将区间[l, n]都加上x但是[r+1,n]我们并不想加x，所以再将[r+1,n]减去x即可。

但是注意，差分数组不能实现“边修改边查询(区间和)，只能实现"多次修改完成后多次查询"。如果要实现“边修改边查询”需要使用树状数组、线段树等数据结构。

二、差分的实现

直接循环O(n)实现即可，注意这里建议使得a[0] = 0，下标从1开始。

for(int i = 1; i <= n; ++i)
    diff[i] = a[i] - a[i - 1];

将区间[l, r]都加上x：

diff[l] += x;
diff[r + 1] -= x;

三、区间更新

用户登录

问题描述

给定一个长度为 n 的数组 a[1], a[2], ..., a[n]。同时给定 m 个操作，每个操作包含三个整数数据 x, y, z。每个操作的意义是给数组中下标为 x 到下标为 y 之间（包括 x 和 y）的元素的值都加上 z。

输入格式

输入包含多组数据，数据组数不大于 5。

每组数据的第一行有两个整数 n, m（0 < n, m < 100），分别表示数组的长度和操作的数量。

第二行有 n 个整数，分别代表 a[1], a[2], ..., a[n]（0 ≤ a[i] < 10）的初始值。

接下来 m 行，每行包含三个整数 x, y, z（1 ≤ x ≤ y ≤ n, 0 < z < 10），表示一个操作。

输出格式

对于每组数据，输出一行，包含这个序列的所有元素的值，并且每个值之间应该以空格隔开。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
vector<int>a(N), b(N);

void solve(int n, int m) {
	for (int i = 1; i <= n; i++)cin >> a[i];
	for (int i = 1; i <= n; i++)b[i] = a[i] - a[i - 1];// 初始化差分数组
	while (m--) {
		int l, r, x; cin >> l >> r >> x;
		b[l] += x; b[r + 1] -= x;  // 区间[l,r] [l]+x    [r+1]-x
	}
	for (int i = 1; i <= n; i++)a[i] = a[i - 1] + b[i];
	for (int i = 1; i <= n; i++)cout << a[i] << " \n"[i == n];必须是双引号，\之前可以写空格或者逗号
}
int main()
{
	int n, m;
	// 输入 n, 表示 a[n] 的元素个数
	// 输入 m, 表示 m 行
	while (cin >> n >> m)solve(n, m);

	return 0;
}

今天就先到这了！！！

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2024-03-03，如有侵权请联系 cloudcommunity@tencent.com 删除

数组