Maxq

Johnie a început să se joace cu un vector de numere. El dispune inițial de un vector $v$ cu $n$ numere întregi (numerotate de la $0$ la $n - 1$) și poate efectua următoarele operații:

• $0 \mbox{ } x \mbox{ } y$: Schimbă elementului de pe poziția $x$ cu numărul $y$.
• $1 \mbox{ } x \mbox{ } y$: Află subsecvența de sumă maximă din $v$ inclusă între indicii $x$ și $y$.

Ajutați-l pe Johnie să efectueze repede operațiile de mai sus.

Exemplu

Soluție

Ideea se bazează pe algoritmul de găsire a subsecvenței de sumă maximă prin divide et impera. Acesta este descris în detaliu în cartea Introduction to Algorithms, paginile 68 - 74. Vom reaminti pe scurt acest algoritm:

Divide: Împărțim vectorul în două jumătăți.

Stăpânește: Calculăm recursiv subsecvența de sumă maximă din fiecare jumătate.

Combină: Subsecvența de sumă maximă din vectorul curent poate fi inclusă complet în prima jumătate, poate fi inclusă complet în a doua jumătate, sau poate să înceapă în prima jumătate și să se termine în a doua. Valorile corespunzătoare primelor două cazuri le avem deja calculate de la etapa precedentă. Mai rămâne de calculat subsecvența de sumă maximă care include mijlocul vectorului. Pe aceasta o putem determina în $O(n)$ astfel: Fixăm poziția de final a subsecvenței din prima jumătate în $[n / 2]$, iar apoi iterăm începutul secvenței de la $[n / 2]$ la $1$, reținând pe parcurs suma maximă a unei astfel de subsecvențe. Similar, calculăm suma pentru jumătatea din dreapta, iar la final le adunăm.

Întorcându-ne la problemă, vom construi un arbore de intervale pentru care vom reține în fiecare nod $[l, r]$ câte un struct cu patru câmpuri:

• $\mathrm{sumAll}$: suma elementelor din interval
• $\mathrm{sumMax}$: suma maximă a unei subsecvențe din interval
• $\mathrm{sumLeft}$: suma maximă a unei subsecvențe din interval, cu capătul din stânga fixat în $l$
• $\mathrm{sumRight}$: suma maximă a unei subsecvențe din interval, cu capătul din dreapta fixat în $r$

Un $\mathrm{query}$ va returna tot un astfel de struct, calculat în acest mod:

• $\mathrm{sumAll = left.sumAll + right.sumAll}$
• $\mathrm{sumMax = max(left.sumMax, right.sumMax, left.sumRight + right.sumLeft)}$
• $\mathrm{sumLeft = max(left.sumLeft, left.sumAll + right.sumLeft)}$
• $\mathrm{sumRight = max(right.sumRight, left.sumRight + right.sumAll)}$

Când facem $\mathrm{update}$, coborâm în arbore până la frunza corespunzătoare poziției date, schimbăm valoarea respectivă, iar apoi ne întoarcem spre rădăcină actualizând nodurile de pe traseu în modul descris mai sus.

Cum la această problemă ideea constă în modelarea operațiilor pe arbore, și nu în utilizarea acestora, mai jos puteți vedea o clasă ce implementează arborele de intervale necesar acestei probleme:

class SegmTree {
  private:
    struct Node {
        long long int sumAll, maxSum;
        long long int maxLeft, maxRight;

        // Constructor pentru nodurile frunză:
        Node(long long int val = 0) {
            sumAll = maxSum = maxLeft = maxRight = val;
        }

        // Operatorul + calculează valoarea unui nod în funcție de fiii săi:
        Node operator+(Node right) {
            Node ret;
            ret.sumAll = sumAll + right.sumAll;
            ret.maxSum = max(maxRight + right.maxLeft, max(maxSum, right.maxSum));
            ret.maxLeft = max(maxLeft, sumAll + right.maxLeft);
            ret.maxRight = max(right.maxRight, right.sumAll + maxRight);
            return ret;
        }
    };

    int n;
    vector<Node> tree;

    void build(int node, int left, int right, vector<long long int>& v) {
        if (left == right) {
            tree[node] = Node(v[left]);
            return;
        }

        int mid = (left + right) / 2;
        build(2 * node, left, mid, v);
        build(2 * node + 1, mid + 1, right, v);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }

    void update(int node, int left, int right, int pos, long long int val) {
        if (left == right) {
            tree[node] = Node(val);
            return;
        }

        int mid = (left + right) / 2;
        if (pos <= mid)
            update(2 * node, left, mid, pos, val);
        else
            update(2 * node + 1, mid + 1, right, pos, val);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }

    Node query(int node, int left, int right, int qLeft, int qRight) {
        if (left == qLeft && right == qRight)
            return tree[node];

        int mid = (left + right) / 2;
        if (qRight <= mid)
            return query(2 * node, left, mid, qLeft, qRight);
        if (qLeft > mid)
            return query(2 * node + 1, mid + 1, right, qLeft, qRight);

        return query(2 * node, left, mid, qLeft, mid) +
               query(2 * node + 1, mid + 1, right, mid + 1, qRight);
    }

  public:
    SegmTree(vector<long long int>& v) {
        n = v.size();
        tree.resize(4 * n);
        build(1, 0, n - 1, v);
    }
    
    void update(int pos, int val) {
        update(1, 0, n - 1, pos, val);
    }

    long long int query(int left, int right) {
        return max(query(1, 0, n - 1, left, right).maxSum, 0);
    }
};