Збирови сегмената - Решење

Директно решење

Директно решење подразумева да све бројеве учитамо у низ, а затим да за сваки упит изнова рачунамо збир одговарајућег сегмента низа.

#include <iostream>
#include <vector>
using namespace std;

int main() {
  // ucitavamo niz
  int n;
  cin >> n;
  vector<int> brojevi(n);
  for (int i = 0; i < n; i++)
    cin >> brojevi[i];
  
  // ucitavamo granice segmenata i izracunavamo i ispisujemo njihove zbirove
  int m;
  cin >> m;
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    int zbir = 0;
    for (int j = a; j <= b; j++)
      zbir += brojevi[j];
    cout << zbir << endl;
  }
  return 0;
}

Збирови префикса

Једноставно ефикасно решење је засновано на наредној идеји: уместо чувања елемената низа, можемо чувати низ збирова префикса низа. Збир сваког сегмента \([l, d]\) можемо разложити на разлику збира префикса до елемента \(d\) и префикса до елемента \(l-1\). Сличну техника је употребљена у задатку Аритметички троугао. Ако користимо ознаку \(\sum_{k=m}^{n} a_k\) која означава збир \(a_m + a_{m+1} + \ldots + a_n\), можемо записати да је

\[\sum_{k=l}^d a_k = \sum_{k=0}^{d} a_k - \sum_{k=0}^{l-1} a_k.\]

Збирови свих префикса се могу израчунати и сместити у додатни (а ако је уштеда меморије битна, онда чак и у оригинални) низ. Дакле, током учитавања елемената можемо формирати низ збирова префикса (рачунаћемо их инкрементално, јер се сваки наредни збир префикса добија увећавањем претходног збира префикса за текући елемент низа). Нека \(z_i\) означава збир елемената префикса одређеног позицијама из интервала \([0, i)\). Формирамо, дакле, низ \(z_i = \sum_{k=0}^{i-1} a_k\) (при чему је \(z_0 = 0\), збир празног префикса). Тада збир елемената у сегменту позиција \([l, d]\) израчунавамо као \(z_{d+1} - z_l\).

#include <iostream>
#include <vector>

using namespace std;

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
  // ucitavamo brojeve i izracunavamo zbirove prefiksa
  int n;
  cin >> n;
  vector<int> zbirovi_prefiksa(n+1);
  zbirovi_prefiksa[0] = 0;
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    zbirovi_prefiksa[i+1] = zbirovi_prefiksa[i] + x;
  }

  // ucitavamo granice segmenata i izracunavamo i ispisujemo njihove zbirove
  int m;
  cin >> m;
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    cout << zbirovi_prefiksa[b+1] - zbirovi_prefiksa[a] << '\n';
  }
  
  return 0;
}