peltorator

Prefix Sums: Basic

Mar 8th, 2021 (edited)
775
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. int main() {
  15.     int n;
  16.     cin >> n;
  17.     vector<int> arr(n);
  18.     for (int& val : arr) {
  19.         cin >> val;
  20.     }
  21.     vector<int> prefixSums = findPrefixSums(arr);
  22.  
  23.     int queriesNumber;
  24.     cin >> queriesNumber;
  25.     for (int i = 0; i < queriesNumber; i++) {
  26.         int left, right;
  27.         cin >> left >> right;
  28.         left--;
  29.         cout << prefixSums[right] - prefixSums[left] << '\n';
  30.     }
  31.     return 0;
  32. }
  33.  
RAW Paste Data