Algoritmi → Strukture podataka → Segmentno stablo

Segmentno stablo

Ideja

Koren stabla odgovara celom nizu [0, n−1]. Svaki čvor koji pokriva [l, r] ima dva deteta: [l, m] i [m+1, r], gde je m = (l+r)/2. Listovi su pojedinačni elementi. U svakom čvoru čuvamo rezultat za njegov interval – za minimum: t[čvor] = min(t[levo], t[desno]).

Čvorove čuvamo u nizu kao kod hipa: koren je 1, deca čvora v su 2v i 2v+1. Niz dužine 4n je uvek dovoljan.

• Upit [ql, qr]: ako je interval čvora potpuno unutar upita – vrati vrednost čvora; ako je potpuno van – vrati neutralnu vrednost (za minimum: beskonačno); inače pitaj oba deteta.
• Izmena pozicije i: spusti se do lista, promeni ga, i na povratku ponovo izračunaj sve pretke.

Kod: minimum na intervalu uz izmene

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

int n;
vector<int> a, t;

void izgradi(int v, int l, int r) {
    if (l == r) { t[v] = a[l]; return; }
    int m = (l + r) / 2;
    izgradi(2 * v, l, m);
    izgradi(2 * v + 1, m + 1, r);
    t[v] = min(t[2 * v], t[2 * v + 1]);
}

int upit(int v, int l, int r, int ql, int qr) {
    if (qr < l || r < ql) return INT_MAX;          // potpuno van upita
    if (ql <= l && r <= qr) return t[v];           // potpuno unutar upita
    int m = (l + r) / 2;
    return min(upit(2 * v, l, m, ql, qr), upit(2 * v + 1, m + 1, r, ql, qr));
}

void izmeni(int v, int l, int r, int i, int x) {
    if (l == r) { t[v] = x; return; }
    int m = (l + r) / 2;
    if (i <= m) izmeni(2 * v, l, m, i, x);
    else izmeni(2 * v + 1, m + 1, r, i, x);
    t[v] = min(t[2 * v], t[2 * v + 1]);           // ponovo izračunaj roditelja
}

int main() {
    int q;
    cin >> n >> q;
    a.resize(n);
    t.assign(4 * n, 0);
    for (int &x : a) cin >> x;
    izgradi(1, 0, n - 1);
    while (q--) {
        int tip, x, y;
        cin >> tip >> x >> y;
        if (tip == 1) izmeni(1, 0, n - 1, x - 1, y);              // a[x] = y
        else cout << upit(1, 0, n - 1, x - 1, y - 1) << "\n";      // min a[x..y]
    }
    return 0;
}

Ulaz i izlaz koriste pozicije od 1, a stablo radi sa pozicijama od 0 – zato x - 1.

Druge operacije i lenja propagacija

Za zbir umesto min piši + i vrati 0 za interval van upita; za maksimum max i INT_MIN; za NZD gcd i 0. Kada izmena ne menja jedan element nego ceo interval (npr. „dodaj 5 na pozicije 3–10“), koristi se lenja propagacija: izmena se zapiše u čvor i spušta deci tek kada su potrebna. Detaljnije: CP-Algorithms – Segment Tree.

Zadaci za vežbu

Za svaki zadatak postoji primer, uputstvo i rešenje. Rešenja su provereno tačna na primerima iz teksta.

Proveri znanje