Suma raspona preko prefiksnih suma

Neka je dat niz celih brojeva \(a\) dužine \(n\). Postoje dva tipa upita:

Opis ulaza

Sa standardnog ulaza se unose celi brojevi \(n\) i \(q\), a zatim i \(n\) elemenata niz \(a\). Nakon toga unosi se \(q\) upita. Svaki upit \(j=1,\ldots,q\) čini tip upita \(t_j \in \{ u, s \}\) i argumenti. Ukoliko je tip upita \(t_j = u\), argumenti upita \(j\) su indeks \(i_j\) (\(0 \leq i_j < n\)) i vrednost \(x_j\), a ukoliko je tip upita \(t_j = s\), argumenti upita \(j\) su indeksi \(l_j\) i \(r_j\) (\(0 \leq l_j \leq r_j < n\)). Pretpostaviti da je broj upita prvog tipa mnogo manji od broja upita drugog tipa.

Opis izlaza

Za svaki upit drugog tipa ispisati traženu sumu.

Primer

Ulaz

8 4
3 1 4 1 5 9 2 6 
s 1 3
s 0 4
u 1 4
s 0 4

Izlaz

6
14
17

Rešenje

Opis glavnog rešenja

Pod pretpostavkom da je broj upita prvog tipa mnogo manji od broja upita drugog tipa, zadatak možemo rešiti pomoću prefiksnih suma. Neka je niz prefiksnih suma \(p\), tj. za svako \(i\) važi \(p_i = \sum_{j=0}^i a_j\). Niz prefiksnih suma možemo inkrementalno sagraditi u vremenskoj složenosti \(O(n)\). Za prvi tip upita \(i\)-tom elementu treba dodeliti novu vrednost, tj. \(a_i \gets x\). Tada treba ažurirati i niz prefiksnih suma \(p\). Složenost ove operacije je \(O(n)\). Drugi tip upita rešavamo tako što iskoristimo niz prefiksnih suma. Naime, važi \(\sum_{j=l}^r a_j = \sum_{j=0}^r a_j - \sum_{j=0}^{l-1} a_j = p_r - p_{l-1}\), za \(l>0\), kao i \(\sum_{j=l}^r a_j = \sum_{j=0}^r a_j = p_r\), za \(l = 0\). Složenost ove operacije je \(O(1)\). Kako je broj upita prvog tipa mnogo manji od broja upita drugog tipa, algoritam možemo smatrati da je složenosti \(O(n + q)\), ali je on suštinski složenosti \(O(nq)\).

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

int main(void)
{
    int n, q;
    cin >> n >> q;

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    vector<int> p(n);
    partial_sum(a.cbegin(), a.cend(), p.begin());

    for (int i = 0; i < q; i++) {
        string query;
        cin >> query;

        if (query == "u") {
            int ind, val;
            cin >> ind >> val;

            a[ind] = val;
            partial_sum(a.cbegin(), a.cend(), p.begin());
        } else if (query == "s") {
            int l, r;
            cin >> l >> r;

            cout << (l == 0 ? p[r] : p[r] - p[l - 1]) << endl;
        }
    }

    return 0;
}