peltorator

Difference Array: Basic

Mar 8th, 2021
989
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.  
RAW Paste Data