Advertisement

# Difference Array: Basic

Mar 8th, 2021
2,069
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <bits/stdc++.h>
2.
3. using namespace std;
4.
5. vector<int> findPrefixSums(const vector<int>& a) {
6.     int n = a.size();
7.     vector<int> prefixSums(n + 1, 0);
8.     for (int i = 0; i < n; i++) {
9.         prefixSums[i + 1] = prefixSums[i] + a[i];
10.     }
11.     return prefixSums;
12. }
13.
14. vector<int> findDiffsArray(const vector<int>& arr) {
15.     int n = arr.size();
16.     vector<int> diffs(n - 1);
17.     for (int i = 0; i < n - 1; i++) {
18.         diffs[i] = arr[i + 1] - arr[i];
19.     }
20.     return diffs;
21. }
22.
23. vector<int> precalc(vector<int> b) {
24.     b.insert(b.begin(), 0); // add leading zero
25.     vector<int> a = findDiffsArray(b);
26.     return a;
27. }
28.
29. vector<int> postcalc(const vector<int>& a) {
30.     vector<int> finalB = findPrefixSums(a);
31.     finalB.erase(finalB.begin()); // delete leading zero
32.     return finalB;
33. }
34.
35. int main() {
36.     int n;
37.     cin >> n;
38.     vector<int> b(n);
39.     for (int &val : b) {
40.         cin >> val;
41.     }
42.     vector<int> diffArr = precalc(b);
43.
44.     auto addOnHalfInterval = [&](int left, int right, int d) { // [left, right) += d
45.         diffArr[left] += d;
46.         if (right < n) {
47.             diffArr[right] -= d;
48.         }
49.     };
50.
51.     int queriesNumber;
52.     cin >> queriesNumber;
53.     for (int i = 0; i < queriesNumber; i++) {
54.         int l, r;
55.         int d;
56.         cin >> l >> r >> d;
57.         l--;
58.         addOnHalfInterval(l, r, d);
59.     }
60.     vector<int> finalB = postcalc(diffArr);
61.     for (int val : finalB) {
62.         cout << val << ' ';
63.     }
64.     cout << endl;
65.     return 0;
66. }
67.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement