10 2018 Lectia1

From Algopedia
Jump to navigationJump to search

Arbori de intervale

Vom introduce arborii de intervale prin exemple de probleme care îi folosesc. Ideea generală este să găsim o structură de date care permite inserarea și ștergerea de intervale, precum și anumite interogări despre intervale, în timp logaritmic. Prin comparație, dacă am stoca un vector de frecvență peste mulțimea coordonatelor, operațiile ar deveni O(lungimea intervalului).

1D: Lungimea reuniunii a n segmente

Enunț: Se dau n segmente pe axa Ox. Să se afle lungimea reuniunii lor.

Există diverse metode de rezolvare în O(n log n).

  • Sortăm cele 2 * n capete de segment, apoi le parcurgem, ținând evidența numărului de segmente suprapuse (incrementăm când întâlnim capătul stâng al unui segment, decrementăm la capătul drept). De câte ori contorul este pozitiv, adăugăm lungimea intervalului curent.
  • Sortăm cele 2 * n coordonate, apoi le normalizăm la mulțimea { 1, ..., 2 * n }. Pentru fiecare element al mulțimii ținem un contor care indică numărul de segmente care acoperă acel interval. Pentru fiecare segment, incrementăm contorul pentru fiecare interval acoperit, în O(1), folosind șmenul lui Mars. La final, însumăm lungimile intervalelor acoperite de cel puțin un segment.

Dacă coordonatele sunt întregi și cuprinse între 0 și W, atunci există și un algoritm în O(n + W) care folosește memorie O(W). Tot folosind șmenul lui Mars, pentru fiecare segment [x, y] incrementăm valorile din vector pe poziții între x și y.

Ce facem dacă dorim să calculăm lungimea reuniunii în mod dinamic? Cu alte cuvinte, să efectuăm în O(log n) operațiile:

  • adaugă un segment la colecție;
  • elimină un segment din colecție;
  • află lungimea reuniunii segmentelor curente.

Această nevoie se regăsește în versiunea 2D a problemei.

2D: Aria (sau perimetrul) reuniunii a n dreptunghiuri

Enunț: Se dau n dreptunghiuri în plan, cu laturile paralele cu axele. Să se afle aria (sau perimetrul) figurii rezultate.

  • prezentarea algoritmului de baleiere
  • reducerea la o problemă 1D
  • arbori de intervale
  • pentru arie, avem nevoie să calculăm, la fiecare moment în cursul baleierii, reuniunea segmentelor active pe linia de baleiere
  • pentru perimetru, avem nevoie doar de numărul de intervale (continue) acoperite de dreptunghiuri; vom calcula, separat, perimetrul pe segmente verticale și pe segmente orizontale
  • așadar, ce stocăm în fiecare nod al arborelui?

Complexitatea rezultată este O(n log n).

Arborele de intervale se reprezintă cel mai eficient în mod similar unui heap. Strict vorbind, când n nu este o putere a lui 2, arborele nu va fi strict; vor exista noduri lipsă pe ultimul nivel. Dacă este important, putem să extindem numărul de noduri (sau distanța maximă acoperită) până la o putere a lui 2. Numai astfel putem garanta că toate frunzele sunt pe același nivel și că fiii nodului x sunt 2x și 2x + 1.

Subliniem că mai există o structură cu un nume asemănător: arborele echilibrat de segmente. Acesta este un arbore echilibrat (de exemplu roșu-negru) augmentat cu informații despre segmente în fiecare nod. Această structură nu face obiectul lecției.

1D: Numărul maxim de segmente suprapuse

Enunț: Se dau n segmente închise pe axa Ox. Să se afle numărul maxim de segmente suprapuse.

Problema 1D anterioară (lungimea reuniunii) se adaptează imediat pentru această problemă.

2D: Numărul maxim de dreptunghiuri suprapuse

Enunț: Se dau n dreptunghiuri închise în plan, cu laturile paralele cu axele. Să se afle numărul maxim de dreptunghiuri suprapuse.

Algoritmul de baleiere de la problema anterioară se adaptează imediat pentru această problemă.

1D: Numărul de segmente intersectate de un punct (stabbing query)

Enunț: Se dau n segmente închise pe axa Ox și m puncte pe axa Ox. Pentru fiecare punct, să se spună în câte segmente este el inclus.

Această problemă este de tipul preprocesare + interogări. Întrucât nu avem de făcut ștergeri, ci doar inserări de segmente, putem folosi și un arbore de segmente. Complexitatea rezultată este O(n log n) pentru preprocesare și O(m log n) pentru a răspunde la interogări.

2D: Numărul de dreptunghiuri intersectate de un punct (stabbing query)

Enunț: Se dau n dreptunghiuri închise în plan, cu laturile paralele cu axele, și m puncte pe axa Ox. Pentru fiecare punct, să se spună în câte dreptunghiuri este el inclus.

Construim un arbore de intervale considerând proiecțiile segmentelor pe axa Ox. În fiecare nod din acest arbore, considerăm numai dreptunghiurile asociate cu acel nod (așadar cele care includ complet intervalul aferent nodului). În nod stocăm un arbore de intervale conținând numai acele dreptunghiuri.

Soluția este O(n log2 n) pentru preprocesare și O(m log2 n) pentru interogări.

1D: Numărul de puncte conținute de un segment (range query)

Enunț: Se dau n puncte închise pe axa Ox și m segmente pe axa Ox. Pentru fiecare segment, să se spună câte puncte conține.

Soluția evidentă este să sortăm punctele și să facem, pentru fiecare segment, două căutări binare. Aceasta ne oferă o complexitate O(n log n) pentru preprocesare și O(log n) per interogare. Dezavantajul este că nu se poate generaliza la spațiul 2D.

O altă soluție de aceeași complexitate se obține construind un arbore echilibrat și căutând, pentru fiecare segment [x, y], coordonatele x și y în arbore.

2D: Numărul de puncte conținute de un dreptunghi (range query)

Enunț: Se dau n puncte închise pe axa Ox și m dreptunghiuri cu laturi paralele cu axele. Pentru fiecare dreptunghi, să se spună câte puncte conține.

O primă soluție, în O(sqrt(n)) per query, construiește un arbore kD (prescurtare de la k-dimensional). În cazul nostru, k = 2. Divizăm binar spațiul prin tăieturi alternative, verticale și orizontale. Obținem astfel celule dreptunghiulare, posibil nemărginite. În frunze se află celule cu exact un punct.

  • Cum construim arborele kD în O(n log n)? Care este relația de recurență?
  • Cum răspundem la o interogare? Există următoarele cazuri:
    • celula v este o frunză
    • celula v este inclusă în dreptunghi
    • celula v este disjunctă de dreptunghi
    • alte cazuri
  • Care este complexitatea?
    • De interes sunt celulele care se intersectează cu dreptunghiul. Câte astfel de celule există?
    • Să considerăm o latură a dreptunghiului și două partiții succesive ale spațiului (una verticală, una orizontală)
    • Rezultă formula de recurență pentru numărul de intersecții: I(n) = 2 I(n/4) + 2, adică I(n) = O(sqrt(n))

O a doua soluție, considerabil mai dificil de implementat, recurge din nou la arbori de intervale pe două niveluri. Construim un arbore de intervale după coordonata X. În fiecare nod v stocăm arborele de intervale al tuturor punctelor conținute în subarborele lui v, ordonate de această dată după coordonata Y.

Complexitatea rezultată este O(n log2 n), iar memoria necesară O(n log n).

Problema Arbint (Infoarena)

Arborii de intervale pot fi utili și pentru probleme care nu implică direct intervale, ca în problema Arbint. Ce stochează în acest caz arborele de intervale?

File:Aint.jpg
Structura arborelui de intervale

Arborele de intervale este o structura de date definita in modul urmator:

Consideram un arbore in care fiecare nod are atribuit un interval, radacinii arborelui fiindu-i atribuit intervalul maxim, [0, n - 1]. Apoi, pentru fiecare frunza a arborelui (cu intervalul [l, r]), efectuam urmatoarele operatii:

  • Daca l != r, cream un fiu stang si un fiu drept al nodului curent.
  • Fiului stang ii atribuim intervalul [l, (l + r) / 2]
  • Fiului drept ii atribuim intervalul [(l + r) / 2 + 1, r]

Procesul descris se opreste in momentul in care toate frunzele arborelui corespund unui interval format dintr-un singur numar.

#include <stdio.h>
#include <stdlib.h>
#define MAXN 100000
 
int v[1 + MAXN];
int aint[1 + 4 * MAXN];
 
inline int maxim(int a, int b){
    return a > b ? a : b;
}
 
int poz, val;
void update(int p, int st, int dr){ //cautam pozitia poz in intervalul [st, dr], care apare in vector pe pozitia p
    if(st == dr) //daca am ajuns la pozitia cautata, updatam valoarea tinuta de aint
        aint[p] = val;
    else{
        int m = (st + dr) / 2;
        if(poz <= m) update(2 * p, st, m);          //daca valoarea cautata este in intervalul [st, m], restrangem cautarea pe intervalul respectiv
        else         update(2 * p + 1, m + 1, dr);  //daca valoarea cautata este in intervalul [m + 1, dr], restrangem cautarea pe intervalul respectiv
        aint[p] = maxim(aint[2 * p], aint[2 * p + 1]); //updatam raspunsul tinut de nodul nostru intermediar
    }
}
 
int left, right;
int rez;
void query(int p, int st, int dr){
    if(st >= left && dr <= right) //daca intervalul curent este inclus in intervalul cautat, procesam informatia
        rez = maxim(rez, aint[p]);
    else{
        int m = (st + dr) / 2;
        if(left <= m) query(2 * p, st, m);         // daca intervalul cautat intersecteaza [st, m], cautam in [st, m]
        if(right > m) query(2 * p + 1, m + 1, dr); //daca intervalul cautat intersecteaza [m + 1, dr], cautam in [m + 1, dr]
    }
}
 
int main(){
    int n, m;
    FILE*fi,*fo;
    fi=fopen("arbint.in","r");
    fo=fopen("arbint.out","w");

    fscanf(fi,"%d%d", &n, &m);
    for(int i = 1; i <= n; i++){
        fscanf(fi,"%d", &v[i]);
        poz = i, val = v[i];
        update(1, 1, n);
    }
    for(int i=1;i<=m;i++){
        int c, a, b;
        fscanf(fi,"%d%d%d", &c, &a, &b);
        if(c == 0){
            left = a, right = b, rez = 0;
            query(1, 1, n);
            fprintf(fo,"%d\n", rez);
        }
        else{
            poz = a, val = b;
            update(1, 1, n);
        }
    }
    return 0;
}
// Sursa Tinca Matei

#include <bits/stdc++.h>

using namespace std;

// Constantele din problema
const int MAX_N = 8;
const int MAX_2N = 2 * MAX_N;

// Starea dinamicii
double best[1 << MAX_2N];

// Punctele din problema
int x[MAX_2N], y[MAX_2N];

double dist(double xa, double ya, double xb, double yb) {
    return sqrt((xa - xb) * (xa - xb) + (ya - yb) * (ya - yb));
}

int main() {
    int n;
    FILE *fin = fopen("xd.in", "r");
    fscanf(fin, "%d", &n);
    for(int i = 0; i < 2 * n; ++i)
        fscanf(fin, "%d%d", &x[i], &y[i]);
    fclose(fin);

    // Initializam totul cu infinit
    for(int i = 0; i < (1 << MAX_2N); ++i)
        best[i] = 1000000000.0f;
    best[0] = 0.0f;

    // Aplicam formula de recurenta
    for(int mask = 1; mask < (1 << (2 * n)); ++mask) {
        for(int i = 0; i < 2 * n; ++i)
            for(int j = i + 1; j < 2 * n; ++j)
                if((mask & (1 << i)) > 0 && (mask & (1 << j)) > 0)
                    best[mask] = min(best[mask], best[mask ^ (1 << i) ^ (1 << j)] +
                                                 dist(x[i], y[i], x[j], y[j]));
    }

    FILE *fout = fopen("xd.out", "w");
    fprintf(fout, "%.10f", best[(1 << (2 * n)) - 1]);
    fclose(fout);
    return 0;
}

/* Fie dp[multime]
Recurenta este urmatoarea:
dp[mask] = min(dp[mask \ {i, j}] + dist(i, j) unde i si j apartin multimii mask si i != j)

*/

Aplicatii