Sari la conținut

Arbori de intervale (căutare binară, lazy propagation) ● ● ● ● ●

Autor: Ștefan-Cosmin Dăscălescu

Cunoștințe necesare

Introducere#

Așa cum ați văzut și în articolul anterior pe această temă, arborii de intervale se dovedesc a fi o structură de date foarte puternică, care ne ajută în foarte multe tipuri de probleme. În cele ce urmează, vom prezenta un set de operații adiționale pe care le putem face folosind arborii de intervale, precum căutarea binară pe un arbore de intervale, precum și actualizări pe interval, folosind metoda lazy propagation.

Căutarea binară pe un arbore de intervale#

Să presupunem că avem de rezolvat următoarea problemă:

Se da un șir de \(n\) valori și \(q\) queryuri în care fie schimbăm o valoare din șir, fie trebuie să aflăm prima poziție care are o valoare mai mare sau egală cu un \(x\) dat.

O soluție care este foarte simplu de implementat ar fi să folosim o căutare binară pe rezultat, iar la un pas al căutării binare, să folosim un arbore de intervale care să ne răspundă rapid la un query de tipul care este valoarea maximă în intervalul \([1, mid]\).

Deși această soluție rulează în \(\mathcal{O}(q \log^2 n)\), poate fi prea înceată în anumite situații. De aceea, se impune găsirea unor optimizări care să ne permită să nu mai avem nevoie de o altă căutare binară.

Dacă ne gândim la un interval de tipul \([a, b]\), noi vom putea efectua următoarea operație fără probleme, până când ajungem la un interval de lungime \(1\):

  • aflăm primul interval inclus în intervalul \([a, b]\).
  • dacă acest interval are un maxim mai mare sau egal ca \(x\), atunci căutăm în acest subinterval
  • altfel, vom căuta în subintervalele de la dreapta.

Astfel, am demonstrat că putem folosi o strategie de tip divide et impera pentru a aborda această problemă, așa cum se poate vedea în segmentul de cod de mai jos:

int query(int node, int start, int end, int query_start, int query_end, int x) {
    // nu există valoarea
    if (end < query_start || start > query_end) {
        return -1;
    }

    if (start == end) {
        if (segtree[start] >= x) {
            return start;
        }

        // nu am găsit valoarea
        return -1;
    }

    int mid = start + (end - start) / 2;
    int left_result = query(node << 1, start, mid, query_start, query_end, x);
    if (left_result != -1) {
        return left_result;
    }

    return query(node << 1 | 1, mid + 1, end, query_start, query_end, x);
}

Problemă exemplu: Hotel Queries - CSES#

Pentru a rezolva această problemă, va trebui să folosim această tehnică pentru a afla prima poziție din șir cu o valoare mai mare decât valoarea dată, iar dacă o găsim, vom scădea \(x\) din valoarea acelui număr pentru a simula procesul prin care oamenii se cazează la hotel.

Mai jos puteți vedea codul sursă pentru problema dată.

#include <iostream>

constexpr int N = 2e5 + 1;
int hotels, groups, rooms[N + 1], segtree[4 * N + 1];

void build(int node, int start, int end) {
    if (start == end) {
        segtree[node] = rooms[start];
        return;
    }
    int mid = start + (end - start) / 2;

    build(node << 1, start, mid);
    build(node << 1 | 1, mid + 1, end);

    segtree[node] = std::max(segtree[node << 1], segtree[node << 1 | 1]);
}

void update(int node, int start, int end, int index, int value) {
    if (start == end) {
        segtree[node] = value;
        return;
    }

    int mid = start + (end - start) / 2;
    if (index <= mid) {
        update(node << 1, start, mid, index, value);
    } else {
        update(node << 1 | 1, mid + 1, end, index, value);
    }

    segtree[node] = std::max(segtree[node << 1], segtree[node << 1 | 1]);
}

int query(int node, int start, int end, int threshold) {
    if (start == end) {
        return start;
    }

    int mid = start + (end - start) / 2;

    if (segtree[node << 1] >= threshold) {
        return query(node << 1, start, mid, threshold);
    }

    return query(node << 1 | 1, mid + 1, end, threshold);
}

int main() {
    std::cin >> hotels >> groups;

    for (int i = 1; i <= hotels; ++i) {
        std::cin >> rooms[i];
    }

    build(1, 1, hotels);
    for (int i = 1; i <= groups; ++i) {
        int required_rooms;
        std::cin >> required_rooms;

        if (segtree[1] < required_rooms) {
            std::cout << 0 << " ";
            continue;
        }

        int hotel_index = query(1, 1, hotels, required_rooms);
        std::cout << hotel_index << " ";

        rooms[hotel_index] -= required_rooms;
        update(1, 1, hotels, hotel_index, rooms[hotel_index]);
    }

    return 0;
}

Actualizări pe interval - Lazy Propagation#

Am văzut până acum în probleme faptul că putem folosi arborii de intervale în mod eficient pentru a putea efectua actualizări pe unele valori precum și interogări pe intervale. Totuși, aceste lucruri nu ne ajută încă să rezolvăm situațiile în care trebuie să schimbăm valorile de pe un interval și să prelucrăm șirul conform acestor operații.

Tehnica folosită în aceste situații este una specifică și se numește lazy propagation și vom putea folosi această tehnică pentru a rezolva problemele ce țin de actualizarea unui interval de valori și răspunderea la aceleași tipuri de queryuri.

Cel mai important principiu pe care îl aplicăm atunci când vom prelucra asemenea actualizări este acela că vom vrea să le amânăm cât mai mult posibil (de aici vine și denumirea de lazy propagation), iar pentru a face asta, în loc să actualizăm fiecare valoare individuală, vom ține evidența existenței acelei actualizări într-un vector auxiliar, lazy, care va avea drept rol păstrarea unei cantități minime de informație care să ne permită să reconstituim actualizările care s-au făcut la un moment dat.

Problemă introductivă: Range Update Queries - CSES#

Aici va trebui să creștem valorile dintr-un interval cu o valoare dată și să aflăm valoarea de la o anumită poziție. Deși această problemă are și alte soluții (precum cea cu arbori indexați binari), aici ne vom concentra pe învățarea acestei noi tehnici.

În cazul acestei probleme, deoarece avem de făcut actualizări pe interval în care creștem valori, asta ne dă motivația și pentru ce vom stoca în vectorul lazy, și anume suma valorilor din queryurile care au atins nodul respectiv, aceasta fiind singura diferență majoră între codul unei probleme obișnuite ce necesită arbori de intervale și problemele cu lazy propagation.

Ulterior, când procesăm o interogare, vom parcurge în jos drumul de la rădăcină la nodul curent și vom procesa actualizările relevante, împărțind în două conținutul queryurilor, eventual unind conținutul queryului cu alte queryuri anterioare.

Observație

Va fi foarte important atunci când trecem într-un nod să procesăm imediat conținutul din lazy pentru a putea asigura păstrarea corectă a valorilor reale din fiecare nod.

Mai jos puteți vedea codul sursă, unde operațiile specifice metodei lazy propagation sunt explicate în detaliu. Se remarcă atenția la detalii atunci când transferăm conținutul unui query de la un nod la unul din fii, precum și faptul că realizăm actualizările imediat ce vizităm un nod.

#include <iostream>
#include <vector>

// range set value, range query for sum segtree, can be easily modified for
// other things
class SegmentTree {
private:
    int size_;
    std::vector<long long> segtree_;
    std::vector<long long> lazy_;

public:
    void init(int size) {
        size_ = size;
        segtree_.resize(1 + 4 * size);
        lazy_.resize(1 + 4 * size);
    }

    void lazy(int node, int start, int end) {
        segtree_[node] += lazy_[node] * (end - start + 1);

        // Dacă nodul curent nu este o frunză
        if (start != end) {
            lazy_[node << 1] += lazy_[node];
            lazy_[node << 1 | 1] += lazy_[node];
        }

        lazy_[node] = 0;
    }

    void build(int node, int start, int end, std::vector<int> &data) {
        if (start == end) {
            segtree_[node] = data[start];
            return;
        }

        int mid = start + (end - start) / 2;

        build(node << 1, start, mid, data);
        build(node << 1 | 1, mid + 1, end, data);

        segtree_[node] = segtree_[node << 1] + segtree_[node << 1 | 1];
    }

    void update(int node, int start, int end, int query_start, int query_end,
                int value) {
        // Dacă avem lazy, actualizăm
        if (lazy_[node]) {
            lazy(node, start, end);
        }

        if (end < query_start || start > query_end) {
            return;
        }

        if (query_start <= start && end <= query_end) {
            lazy_[node] = value;
            lazy(node, start, end);  // actualizăm
            return;
        }

        int mid = start + (end - start) / 2;

        update(node << 1, start, mid, query_start, query_end, value);
        update(node << 1 | 1, mid + 1, end, query_start, query_end, value);

        segtree_[node] = segtree_[node << 1] + segtree_[node << 1 | 1];
    }

    long long query(int node, int start, int end, int query_start,
                    int query_end) {
        // Dacă avem lazy, actualizăm
        if (lazy_[node]) {
            lazy(node, start, end);
        }

        if (end < query_start || start > query_end) {
            return 0;
        }

        if (query_start <= start && end <= query_end) {
            return segtree_[node];
        }

        int mid = start + (end - start) / 2;
        return query(node << 1, start, mid, query_start, query_end)
             + query(node << 1 | 1, mid + 1, end, query_start, query_end);
    }
};

SegmentTree segtree;

int main() {
    int n, queries;
    std::cin >> n >> queries;

    segtree.init(n);

    std::vector<int> values(n + 1);
    for (int i = 1; i <= n; i++) {
        std::cin >> values[i];
    }

    segtree.build(1, 1, n, values);

    for (int i = 1; i <= queries; i++) {
        int t;
        std::cin >> t;

        if (t == 1) {
            int start, end, value;
            std::cin >> start >> end >> value;
            segtree.update(1, 1, n, start, end, value);
        } else {
            int index;
            std::cin >> index;
            std::cout << segtree.query(1, 1, n, index, index) << '\n';
        }
    }

    return 0;
}

Problema Simple - Info1Cup 2019#

Pentru a rezolva această problemă, vom începe prin a precalcula pentru fiecare interval valoarea maximă pară, valoarea maximă impară, valoarea minimă pară și valoarea minimă impară, deoarece o observație importantă este faptul că adăugarea unei valori pe un interval nu va schimba ordinea relativă a acestor valori.

Astfel, vom păstra pentru fiecare nod în lazy un contor care ține cont de suma actualizărilor efectuate la acea poziție, pentru a stabili dacă trebuie să luăm valorile originale sau cele inverse (minim par/maxim impar) sau (maxim par/minim impar).

Apoi, vom avea grijă la implementarea soluției finale să includem aceste date în răspunsul final.

#include <iostream>
#include <vector>

struct str {
    long long min_even, max_even;
    long long min_odd, max_odd;
};

class SegmentTree {
private:
    int size_;
    std::vector<str> segtree_;
    std::vector<long long> lazy_;

public:
    void init(int sz) {
        size_ = sz;
        segtree_.resize(1 + 4 * sz);
        lazy_.resize(1 + 4 * sz);
    }

    void lazy(int node, int start, int end) {
        if (segtree_[node].min_even != -1) {
            segtree_[node].min_even += lazy_[node];
            segtree_[node].max_even += lazy_[node];
        }

        if (segtree_[node].min_odd != -1) {
            segtree_[node].min_odd += lazy_[node];
            segtree_[node].max_odd += lazy_[node];
        }

        if (lazy_[node] % 2 == 1) {
            std::swap(segtree_[node].min_odd, segtree_[node].min_even);
            std::swap(segtree_[node].max_odd, segtree_[node].max_even);
        }

        if (start != end) {
            lazy_[node << 1] += lazy_[node];
            lazy_[node << 1 | 1] += lazy_[node];
        }

        lazy_[node] = 0;
    }

    str cmp(str lhs, str rhs) {
        str ans = {-1, -1, -1, -1};

        if (lhs.min_even != -1) {
            ans.min_even = lhs.min_even;
        }

        if (ans.min_even == -1
            || (rhs.min_even != -1 && rhs.min_even < ans.min_even)) {
            ans.min_even = rhs.min_even;
        }

        if (lhs.min_odd != -1) {
            ans.min_odd = lhs.min_odd;
        }

        if (ans.min_odd == -1
            || (rhs.min_odd != -1 && rhs.min_odd < ans.min_odd)) {
            ans.min_odd = rhs.min_odd;
        }

        if (lhs.max_even != -1) {
            ans.max_even = lhs.max_even;
        }

        if (ans.max_even == -1
            || (rhs.max_even != -1 && rhs.max_even > ans.max_even)) {
            ans.max_even = rhs.max_even;
        }

        if (lhs.max_odd != -1) {
            ans.max_odd = lhs.max_odd;
        }

        if (ans.max_odd == -1
            || (rhs.max_odd != -1 && rhs.max_odd > ans.max_odd)) {
            ans.max_odd = rhs.max_odd;
        }

        return ans;
    }

    void build(int node, int start, int end, std::vector<int> &data) {
        if (start == end) {
            if (data[start] % 2 == 0) {
                segtree_[node] = {data[start], data[start], -1, -1};
            } else {
                segtree_[node] = {-1, -1, data[start], data[start]};
            }
            return;
        }

        int mid = start + (end - start) / 2;

        build(node << 1, start, mid, data);
        build(node << 1 | 1, mid + 1, end, data);
        segtree_[node] = cmp(segtree_[node << 1], segtree_[node << 1 | 1]);
    }

    void update(int node, int start, int end, int query_start, int query_end,
                int val) {
        if (lazy_[node]) {
            lazy(node, start, end);
        }

        if (end < query_start || start > query_end) {
            return;
        }

        if (query_start <= start && end <= query_end) {
            lazy_[node] = val;
            lazy(node, start, end);
            return;
        }

        int mid = start + (end - start) / 2;

        update(node << 1, start, mid, query_start, query_end, val);
        update(node << 1 | 1, mid + 1, end, query_start, query_end, val);

        segtree_[node] = cmp(segtree_[node << 1], segtree_[node << 1 | 1]);
    }

    str query(int node, int start, int end, int query_start, int query_end) {
        if (lazy_[node]) {
            lazy(node, start, end);
        }

        if (end < query_start || start > query_end) {
            return {-1, -1, -1, -1};
        }

        if (query_start <= start && end <= query_end) {
            return segtree_[node];
        }

        int mid = start + (end - start) / 2;
        return cmp(query(node << 1, start, mid, query_start, query_end),
                   query(node << 1 | 1, mid + 1, end, query_start, query_end));
    }
};

SegmentTree segtree;
int main() {
    int n;
    std::cin >> n;

    segtree.init(n);

    std::vector<int> values(n + 1);
    for (int i = 1; i <= n; i++) {
        std::cin >> values[i];
    }

    int queries;
    std::cin >> queries;

    segtree.build(1, 1, n, values);

    for (int i = 1; i <= queries; i++) {
        int t;
        std::cin >> t;

        if (t == 0) {
            int start, end, value;
            std::cin >> start >> end >> value;
            segtree.update(1, 1, n, start, end, value);
        } else {
            int start, end;
            std::cin >> start >> end;
            str ans = segtree.query(1, 1, n, start, end);
            std::cout << ans.min_even << " " << ans.max_odd << '\n';
        }
    }
    return 0;
}

Problema Range Updates and Sums CSES#

Pentru a rezolva această problemă, va trebui să fim atenți la diferitele tipuri de operații pe care le primim, precum și cum codificăm schimbările (sumă sau schimbarea unei valori), lucruri ce se pot face doar cu o implementare clară a structurii de date folosite.

Pentru a nu folosi mai mulți vectori de tip lazy, am codificat schimbările de valori cu numere negative și adăugările cu numere pozitive, pentru a ști tipul de operație folosit. Ulterior, queryurile de sumă devin asemănătoare celor obișnuite.

Mai jos găsiți soluția care ia accepted.

#include <iostream>
#include <vector>

class SegmentTree {
private:
    int size_;
    std::vector<long long> segtree_;
    std::vector<long long> lazy_;

public:
    void init(int size) {
        size_ = size;
        segtree_.resize(1 + 4 * size);
        lazy_.resize(1 + 4 * size);
    }

    void lazy(int node, int start, int end) {
        if (lazy_[node] > 0) {
            segtree_[node] += lazy_[node] * (end - start + 1);
        } else {
            segtree_[node] = (-lazy_[node]) * (end - start + 1);
        }

        if (start != end) {
            if (lazy_[node] < 0) {
                lazy_[node << 1] = lazy_[node];
                lazy_[node << 1 | 1] = lazy_[node];
            } else {
                if (lazy_[node << 1] < 0) {
                    lazy_[node << 1] -= lazy_[node];
                } else {
                    lazy_[node << 1] += lazy_[node];
                }

                if (lazy_[node << 1 | 1] < 0) {
                    lazy_[node << 1 | 1] -= lazy_[node];
                } else {
                    lazy_[node << 1 | 1] += lazy_[node];
                }
            }
        }

        lazy_[node] = 0;
    }

    void build(int node, int start, int end, std::vector<int> &data) {
        if (start == end) {
            segtree_[node] = data[start];
            return;
        }

        int mid = start + (end - start) / 2;

        build(node << 1, start, mid, data);
        build(node << 1 | 1, mid + 1, end, data);

        segtree_[node] = segtree_[node << 1] + segtree_[node << 1 | 1];
    }

    void update(int node, int start, int end, int query_start, int query_end,
                int value) {
        if (lazy_[node]) {
            lazy(node, start, end);
        }

        if (end < query_start || start > query_end) {
            return;
        }

        if (query_start <= start && end <= query_end) {
            lazy_[node] = value;
            lazy(node, start, end);
            return;
        }

        int mid = start + (end - start) / 2;

        update(node << 1, start, mid, query_start, query_end, value);
        update(node << 1 | 1, mid + 1, end, query_start, query_end, value);

        segtree_[node] = segtree_[node << 1] + segtree_[node << 1 | 1];
    }

    long long query(int node, int start, int end, int query_start,
                    int query_end) {
        if (lazy_[node]) {
            lazy(node, start, end);
        }

        if (end < query_start || start > query_end) {
            return 0;
        }

        if (query_start <= start && end <= query_end) {
            return segtree_[node];
        }

        int mid = start + (end - start) / 2;

        return query(node << 1, start, mid, query_start, query_end)
             + query(node << 1 | 1, mid + 1, end, query_start, query_end);
    }
};

SegmentTree segtree;
int main() {
    int n, queries;
    std::cin >> n >> queries;

    segtree.init(n);

    std::vector<int> values(n + 1);
    for (int i = 1; i <= n; i++) {
        std::cin >> values[i];
    }

    segtree.build(1, 1, n, values);

    for (int i = 1; i <= queries; i++) {
        int t;
        std::cin >> t;

        int start, end, value;
        std::cin >> start >> end;

        if (t == 1) {
            std::cin >> value;
            segtree.update(1, 1, n, start, end, value);
        } else if (t == 2) {
            std::cin >> value;
            segtree.update(1, 1, n, start, end, -value);
        } else if (t == 3) {
            std::cout << segtree.query(1, 1, n, start, end) << '\n';
        }
    }

    return 0;
}

Concluzii#

Căutarea binară în arborele de intervale, precum și lazy propagation sunt tehnici foarte des utilizate în aceste probleme, fiind la baza multor aplicații, așa cum ați putut observa în acest articol. O recomandare pe care o oferim este aceea de a ști foarte bine cum să implementați lazy propagation deoarece această variație a arborilor de intervale poate pune dificultăți dacă nu este abordată cum trebuie.

Recomandăm abordarea unui număr cât mai mare de probleme dintre cele prezentate aici, precum și a problemelor de pe CSES de la secțiunea Range Queries.

Probleme suplimentare#

Resurse suplimentare#