住房与城市建设部网站,北京公司网站制作流程,深圳勘察设计协会,优化推广网站排名一、差分的特点和原理
对于一个数组a[]#xff0c;差分数组diff[]的定义是: 对差分数组做前缀和可以还原为原数组: 利用差分数组可以实现快速的区间修改#xff0c;下面是将区间[l, r]都加上x的方法:
diff[l] x;
diff[r 1] - x;在修改完成后#xff0c;需要做前缀和恢复…一、差分的特点和原理
对于一个数组a[]差分数组diff[]的定义是: 对差分数组做前缀和可以还原为原数组: 利用差分数组可以实现快速的区间修改下面是将区间[l, r]都加上x的方法:
diff[l] x;
diff[r 1] - x;在修改完成后需要做前缀和恢复为原数组所以上面这段代码的含义是:
diff[l]x表示将区间[l, n]都加上x但是[r1,n]我们并不想加x所以再将[r1,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, m0 n, m 100分别表示数组的长度和操作的数量。
第二行有 n 个整数分别代表 a[1], a[2], ..., a[n]0 ≤ a[i] 10的初始值。
接下来 m 行每行包含三个整数 x, y, z1 ≤ x ≤ y ≤ n, 0 z 10表示一个操作。
输出格式
对于每组数据输出一行包含这个序列的所有元素的值并且每个值之间应该以空格隔开。 #include bits/stdc.h
using namespace std;
const int N 1e5 9;
vectorinta(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 [r1]-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;
}今天就先到这了 看到这里了还不给博主扣个 ⛳️ 点赞☀️收藏 ⭐️ 关注
你们的点赞就是博主更新最大的动力 有问题可以评论或者私信呢秒回哦。
