Naivna suma raspona

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 veći 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 
u 2 5
u 3 2
u 1 4
s 0 4

Izlaz

14

Rešenje

Opis glavnog rešenja

Pod pretpostavkom da je broj upita prvog tipa mnogo veći od broja upita drugog tipa, zadatak možemo rešiti naivno. Za prvi tip upita jednostavno \(i\)-tom elementu dodelimo novu vrednost, tj. \(a_i \gets x\). Složenost ove operacije je \(O(1)\). Drugi tip upita rešavamo tako što inkrementalno uvećavamo sumu elementima niza od pozicije \(l\) do pozicije \(r\). Složenost ove operacije je u najgorem slučaju \(O(n)\). Kako je broj upita prvog tipa mnogo veći 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>

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];
    }

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

        if (query == "u") {
            int ind, val;
            cin >> ind >> val;
            a[ind] = val;
        } else if (query == "s") {
            int l, r;
            cin >> l >> r;

            int sum = 0;
            for (int i = l; i <= r; i++) {
                sum += a[i];
            }
            cout << sum << endl;
        }
    }

    return 0;
}