peltorator

Prefix Sums: Structs

Mar 8th, 2021 (edited)
462
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. struct SegmentSumStructure {
  6.     vector<int> prefixSums;
  7.  
  8.     SegmentSumStructure(const vector<int>& a) {
  9.         int n = a.size();
  10.         prefixSums.assign(n + 1, 0);
  11.         for (int i = 0; i < n; i++) {
  12.             prefixSums[i + 1] = prefixSums[i] + a[i];
  13.         }
  14.     }
  15.  
  16.     int findSum(int left, int right) { // [left; right)
  17.         return prefixSums[right] - prefixSums[left];
  18.     }
  19.  
  20. };
  21.  
  22. int main() {
  23.     int n;
  24.     cin >> n;
  25.     vector<int> arr(n);
  26.     for (int& val : arr) {
  27.         cin >> val;
  28.     }
  29.     SegmentSumStructure myAdder(arr);
  30.  
  31.     int queriesNumber;
  32.     cin >> queriesNumber;
  33.     for (int i = 0; i < queriesNumber; i++) {
  34.         int left, right;
  35.         cin >> left >> right;
  36.         left--;
  37.         cout << myAdder.findSum(left, right) << '\n';
  38.     }
  39.     return 0;
  40. }
  41.  
RAW Paste Data