Oibek

Prefix of sum

Apr 29th, 2018
153
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main()
  5. {
  6.     int n, q; cin >> n >> q; //n элементов вектора, q запросов
  7.     vector <int> v(n);
  8.     for (int i = 0; i<n; i++) cin >> v[i];
  9.  
  10.     vector <int> sumV(n); //Вектор, хранящий сумму до n-ого элемента
  11.     int sum = 0;
  12.     for (int i = 0; i<n; i++)
  13.     {
  14.         sum += v[i];
  15.         sumV[i] = sum;
  16.     }
  17.  
  18.     vector <int> ans; //Сюда сохраним ответы
  19.     while (q--)
  20.     {
  21.         int l, r; //Границы, где нужно вывести сумму элементов из [l, r]
  22.         cin >> l >> r;
  23.  
  24.         if (l-2 < 0) ans.push_back(sumV[r-1]);
  25.         else ans.push_back(sumV[r-1] - sumV[l-2]);
  26.         //Необходимая сумма элементов получается из разности суммы
  27.         //элементов из [1, r] и [1, l-1]. Нужно помнить, что индексы начинаются с 0
  28.     }
  29.  
  30.     for (int i = 0; i<ans.size(); i++) cout << ans[i] << " ";
  31. }
  32.  
  33.  
  34. /* Приведу тест. Четыре элементы. Четыре запроса.
  35. 4 4
  36. 5 3 2 11
  37. 1 3
  38. 1 1
  39. 4 4
  40. 1 4
  41. Вывод: 10 5 11 21
  42. */
Add Comment
Please, Sign In to add comment