Week5：前缀和

Week5：前缀和

题目内容
现有n个点，每个点具有一个价值v。
执行q次操作：每次操作给出一个区间[l,r]，和一个值c，对于此区间中的每个点，使其价值v加上c。
给出q次操作之后每个点的值。

输入格式
第一行给出两个整数n,q (1≤n,q≤2⋅10⁵)，分别对应点的数目和操作的数目。
第二行给出n个数a1,a2,…,an (−10⁶≤ai≤10⁶)，分别对应n个点的初始价值。
接下来q行，每行给出三个数l,r和c (1≤l≤r≤n,−10⁵≤c≤10⁵)，分别对应每次操作的三个数。

输出格式
输出一行，表示q次操作之后的各个点的价值v。

输入样例

4 2
-3 6 8 4
4 4 -2
3 3 1

输出样例

-3 6 9 2

输入样例

1 2
0
1 1 -8
1 1 -6

输出样例

-14

解题思路
直接暴力，时间复杂度O(qn),瞬间爆炸。
但是对于某个数组A[n]，我们可以设置一个差分数组B[n]
使对于每个i，有B[i]=A[i]-A[i-1] (i=1时，B[i]=A[i])。

这样，对于每次操作，我们只需要操作区间的两个边界：
A[l,r] += c ⇔ B[l] += c, B[r+1] -= c，中间所有的B[i]，由于是差分数组，所以都不变。

q次操作后得到的差分数组，只需要反着求A[i]即可，时间复杂度O(n+q)。

注意数据大小，记得使用long long类型。

#include <iostream>
#include <vector>
typedef long long ll;
using namespace std;ll B[1000001];int main()
{ios::sync_with_stdio(false);int n, q;cin >> n >> q;ll tm, tn;for (int i = 1; i <= n; i++){cin >> tm;if (i == 1){B[i] = tm;}else{B[i] = tm - tn;}tn = tm;}tm = 1000001;B[n + 1] = tm - tn;int l, r, c;for (int op = 0; op < q; op++){cin >> l >> r >> c;B[l] += c;B[r + 1] -= c;}for (int i = 1; i <= n; i++){if (i == 1){tm = B[i];}else{tm = B[i] + tn;}cout << tm << ' ';tn = tm;}
}

Week5：前缀和

题目内容
现有n个点，每个点具有一个价值v。
执行q次操作：每次操作给出一个区间[l,r]，和一个值c，对于此区间中的每个点，使其价值v加上c。
给出q次操作之后每个点的值。

输入格式
第一行给出两个整数n,q (1≤n,q≤2⋅10⁵)，分别对应点的数目和操作的数目。
第二行给出n个数a1,a2,…,an (−10⁶≤ai≤10⁶)，分别对应n个点的初始价值。
接下来q行，每行给出三个数l,r和c (1≤l≤r≤n,−10⁵≤c≤10⁵)，分别对应每次操作的三个数。

输出格式
输出一行，表示q次操作之后的各个点的价值v。

输入样例

4 2
-3 6 8 4
4 4 -2
3 3 1

输出样例

-3 6 9 2

输入样例

1 2
0
1 1 -8
1 1 -6

输出样例

-14

解题思路
直接暴力，时间复杂度O(qn),瞬间爆炸。
但是对于某个数组A[n]，我们可以设置一个差分数组B[n]
使对于每个i，有B[i]=A[i]-A[i-1] (i=1时，B[i]=A[i])。

这样，对于每次操作，我们只需要操作区间的两个边界：
A[l,r] += c ⇔ B[l] += c, B[r+1] -= c，中间所有的B[i]，由于是差分数组，所以都不变。

q次操作后得到的差分数组，只需要反着求A[i]即可，时间复杂度O(n+q)。

注意数据大小，记得使用long long类型。

#include <iostream>
#include <vector>
typedef long long ll;
using namespace std;ll B[1000001];int main()
{ios::sync_with_stdio(false);int n, q;cin >> n >> q;ll tm, tn;for (int i = 1; i <= n; i++){cin >> tm;if (i == 1){B[i] = tm;}else{B[i] = tm - tn;}tn = tm;}tm = 1000001;B[n + 1] = tm - tn;int l, r, c;for (int op = 0; op < q; op++){cin >> l >> r >> c;B[l] += c;B[r + 1] -= c;}for (int i = 1; i <= n; i++){if (i == 1){tm = B[i];}else{tm = B[i] + tn;}cout << tm << ' ';tn = tm;}
}