Prefiksne sume

Napisati klasu PrefiksneSume koja predstavlja niz celih brojeva, ali ne čuva sam niz, već njegove prefiksne sume. Za čuvanje podataka koristiti klasu DinamickiNiz<T> iz zaglavlja dinamicki_niz.h.

class PrefiksneSume {
public:
    PrefiksneSume();
    std::size_t velicina() const;
    void dodaj(long long x);
    void ukloni_poslednji();
    long long zbir(std::size_t i, std::size_t j) const;
    long long najveci() const;
};

Program obrađuje komande:

Komanda Značenje Složenost Nivo
D x dodaj x na kraj amortizovano $O(1)$ osnovno
S i j ispiši zbir elemenata na pozicijama i..j ($0 \le i \le j &lt;$ broj elemenata) $O(1)$ osnovno
U ukloni poslednji element (niz nije prazan) $O(1)$ dodatno
M ispiši najveći element (niz nije prazan) $O(1)$ izazov

Pitanje za razmišljanje: Zašto zbir ne staje u int? Šta tačno treba da važi za članove klase (invarijanta) posle svake komande?

Ulaz

U prvom redu učitava se broj komandi q $(1 \le q \le 2 \cdot 10^5)$, a zatim q komandi. Vrednosti su do $10^9$ po apsolutnoj vrednosti.

Izlaz

Za svaku komandu S i M ispisati rezultat u posebnom redu.

Primer

Ulaz

9
D 3
D -1
D 4
S 0 2
S 1 1
M
U
M
S 0 1

Izlaz

6
-1
4
3
2

Postavka

main.cpp

#include <iostream>

#include "dinamicki_niz.h"

namespace matf {

    // Niz celih brojeva u koji se dodaje na kraj i iz kog se brise sa kraja;
    // zbir bilo kog segmenta i najveci element dobijaju se u vremenu O(1).
    class PrefiksneSume {
    private:
        // Ovde ide vasa implementacija

    public:
        PrefiksneSume();

        std::size_t velicina() const;

        void dodaj(long long x);
        void ukloni_poslednji();

        long long zbir(std::size_t i, std::size_t j) const;
        long long najveci() const;
    };

    // Ovde ide vasa implementacija

} // namespace matf

int main()
{
    matf::PrefiksneSume niz;

    int q;
    std::cin >> q;
    for (int k = 0; k < q; ++k) {
        char komanda;
        std::cin >> komanda;
        if (komanda == 'D') {
            long long x;
            std::cin >> x;
            niz.dodaj(x);
        } else if (komanda == 'S') {
            std::size_t i, j;
            std::cin >> i >> j;
            std::cout << niz.zbir(i, j) << std::endl;
        } else if (komanda == 'U') {
            niz.ukloni_poslednji();
        } else if (komanda == 'M') {
            std::cout << niz.najveci() << std::endl;
        }
    }

    return 0;
}

Rešenje

main.cpp

#include <iostream>

#include "dinamicki_niz.h"

namespace matf {

    // Niz celih brojeva u koji se dodaje na kraj i iz kog se brise sa kraja;
    // zbir bilo kog segmenta i najveci element dobijaju se u vremenu O(1).
    class PrefiksneSume {
    private:
        // Invarijanta (n je broj elemenata):
        //   prefiks ima n + 1 elemenata, prefiks[k] je zbir prvih k elemenata;
        //   maksimumi ima n elemenata, maksimumi[k] je najveci od prvih k + 1.
        // Oba niza se menjaju samo na kraju, pa dodaj i ukloni_poslednji
        // ne moraju nista da preracunavaju.
        DinamickiNiz<long long> prefiks;
        DinamickiNiz<long long> maksimumi;

    public:
        PrefiksneSume();

        std::size_t velicina() const;

        void dodaj(long long x);
        void ukloni_poslednji();

        long long zbir(std::size_t i, std::size_t j) const;
        long long najveci() const;
    };

    PrefiksneSume::PrefiksneSume()
    {
        prefiks.dodaj(0);
    }

    std::size_t PrefiksneSume::velicina() const
    {
        return maksimumi.velicina();
    }

    void PrefiksneSume::dodaj(long long x)
    {
        // Nove vrednosti se racunaju u lokalnim promenljivama: argument za
        // dodaj ne sme biti referenca na element niza koji se realocira
        // (npr. std::max(maksimumi.poslednji(), x) vraca referencu).
        long long novi_prefiks = prefiks.poslednji() + x;
        prefiks.dodaj(novi_prefiks);

        long long novi_maksimum = x;
        if (!maksimumi.prazan() && maksimumi.poslednji() > x)
            novi_maksimum = maksimumi.poslednji();
        maksimumi.dodaj(novi_maksimum);
    }

    void PrefiksneSume::ukloni_poslednji()
    {
        assert(velicina() > 0);
        prefiks.obrisi_poslednji();
        maksimumi.obrisi_poslednji();
    }

    long long PrefiksneSume::zbir(std::size_t i, std::size_t j) const
    {
        assert(i <= j && j < velicina());
        return prefiks[j + 1] - prefiks[i];
    }

    long long PrefiksneSume::najveci() const
    {
        return maksimumi.poslednji();
    }

} // namespace matf

int main()
{
    matf::PrefiksneSume niz;

    int q;
    std::cin >> q;
    for (int k = 0; k < q; ++k) {
        char komanda;
        std::cin >> komanda;
        if (komanda == 'D') {
            long long x;
            std::cin >> x;
            niz.dodaj(x);
        } else if (komanda == 'S') {
            std::size_t i, j;
            std::cin >> i >> j;
            std::cout << niz.zbir(i, j) << std::endl;
        } else if (komanda == 'U') {
            niz.ukloni_poslednji();
        } else if (komanda == 'M') {
            std::cout << niz.najveci() << std::endl;
        }
    }

    return 0;
}