focusG

Info

nr. 1

5/4

- ap

rilie 2

005

35

Arbori de intervale Un arbore de intervale este un arbo-re binar în care fiecare nod poate aveaasociatã o structurã auxiliarã (anumi-te informaþii).

Dându-se douã numere întregi stºi dr, cu st < dr, atunci arborele deintervale T(st, dr) se construieºte re-cursiv astfel:• considerãm rãdãcina nod având

asociat intervalul [st, dr];• dacã st < dr atunci, vom avea aso-

ciat subarborele stâng T(st, mij),respectiv subarborele drept T(mij +1, dr), unde mij este mijlocul inter-valului [st, dr].

Intervalul [st, dr] asociat unuinod se numeºte interval standard.Frunzele arborelui sunt considerateintervale elementare, ele având lun-gimea 1. Un arbore de intervale esteilustrat în figura 1.

ProprietateUn arbore de intervale este un arbo-re binar echilibrat (diferenþa absolutãîntre adâncimea subarborelui stâng ºisubarborelui drept este cel mult 1).Astfel adâncimea unui arbore de in-tervale care conþine N intervale este[log2 N] + 1.

Vom prezenta în cele ce urmeazãoperaþiile specifice acestei structuride date.

Actualizarea unui interval din-tr-un arbore de intervaleVom prezenta pseudocodul unei pro-ceduri recursive cu ajutorul cãreia sepoate insera un interval [a, b] într-unarbore de intervale T(st, dr) cu rãdã-cina în nodul nod.

Cea mai eficientã metodã de sto-care în memorie a unui arbore de in-tervale este utilizarea unui vector fo-losind aceeaºi codificare a nodurilor

ca ºi cea utilizatã în cazul heap-urilorbinare.

procedura Actualizare

(nod, st, dr, a, b)

dacă a ≤ st și dr ≤ b atunci

modificã structura auxiliarãdin nodul nod

altfel

mij ← [(st + dr) / 2]

dacă a ≤ mij atunci

Actualizare(2 · nod, st,

mij, a, b)

sfârșit dacă

dacă b > mij atunci

Actualizare(2 · nod + 1,

mij + 1, dr, a, b)

sfârșit dacă

actualizeazã structura auxiliarãdin nodul nod

sfârșit dacă

sfârșit procedură

Interogarea unui interval din-tr-un arbore de intervaleVom prezenta în continuare pseudo-codul unei funcþii recursive care re-turneazã informaþiile asociate unuiinterval [a, b] dintr-un arbore de in-tervale T(st, dr) cu rãdãcina în nodulnod.

funcţie Interogare

(nod, st, dr, a, b)

dacă a ≤ st și dr ≤ b atunci

returnează structura auxiliarã din nodul nod

altfel

mij ← [(st + dr) / 2]

Structuri de date

Arbori de INTERVALEDana Lica

În cadrul acestui articol vom prezenta o structurã de date cunoscutã subnumele de arbore de intervale (engl. segment tree), precum ºi o serie deaplicaþii în geometria computaþionalã.

FFiigguurraa 11:: AArrbboorree ddee iinntteerrvvaallee

GIn

fo n

r. 1

5/4

- a

pri

lie 2

005

36

focu

sdacă a ≤ mij atunci

Interogare(2 · nod, st,

mij, a, b)

sfârșit dacă

dacă b > mij atunci

Interogare(2 · nod + 1,

mij + 1, dr, a, b)

sfârșit dacă

returnează structura auxiliarãdin fiul stâng ºi din fiul drept

sfârșit dacă

sfârșit funcţie

Analiza complexitãþiiVom demonstra în continuare cã ope-raþiile prezentate mai sus au ordinulde complexitate O(log N) pentru unarbore de N intervale. Este posibil caîntr-un nod sã aibã loc apel atât pen-tru fiul stâng cât ºi pentru cel drept.Acest fapt determinã un cost adiþio-nal doar prima datã când are loc.

Dupã prima "rupere în douã",oricare astfel de "rupere" nu va adu-ce cost adiþional, deoarece unul dinfii va fi mereu inclus complet în in-tervalul [a, b]. Datoritã faptului cãînãlþimea unui arbore de N intervaleeste întotdeauna [log2 N] + 1, ordi-nul de complexitate al operaþiilorprezentate va fi O(log N).

Necesarul de memoriePentru a reþine în memorie un arborede intervale pentru N valori, avea ne-voie de N + N / 2 + N / 4 + N / 8 +… = 2 · N - 1 locaþii de memorie (sunt2 · N - 1 noduri).

Deoarece arborele nu este com-plet, trebuie verificat de fiecare datãdacã fiii unui nod existã în arbore(aceastã verificare a fost omisã în pse-udocodul prezentat anterior), altfels-ar încerca accesarea de valori dinvector care nu existã.

Dacã memoria disponibilã estesuficientã, se poate declara vectorulcare reþine arborele de intervale delungime 2K astfel încât 2K ≥ 2 · N - 1,simulând astfel un arbore complet ºinefiind necesare verificãrile menþio-nate mai sus.

AplicaþiiÎn cele ce urmeazã vom prezentaenunþurile câtorva probleme pentru a

cãror rezolvare arborii de intervalesunt utili.

Problema #1Se considerã N ≤ 50.000 segmente înplan dispuse paralel cu axele Ox ºiOy. Sã se determine care este numã-rul total de intersecþii între segmente.

În fiºierul segment.in se aflã peprima linie numãrul N al segmente-lor, iar pe fiecare dintre urmãtoareleN linii se aflã câte patru numere na-turale mai mici decât 50.000, repre-zentând coordonatele carteziene aleextremitãþilor fiecãrui segment.

Rezultatul se va scrie în fiºierulsegment.out.

Exemplusegment.in

5

2 9 13 9

4 6 12 6

1 2 6 2

5 0 5 8

7 5 7 11

segment.out

4

Timp de execuþie: 1 secundã/test

Algoritmi de "baleiere" (linesweeping)Folosind cunoºtinþe generale de geo-metrie analiticã se poate obþine unalgoritm cu ordinul de complexitateO(N2), dar acesta nu se va încadra înlimita de timp.

Pentru rezolvarea acestei proble-me vom folosi o tehnicã ce este cu-noscutã sub numele de "baleiere"(engl. sweeping) care este comunã

multor algoritmi de geometrie com-putaþionalã.

Pentru operaþia de baleiere, odreaptã de baleiere verticalã, imagi-narã, traverseazã mulþimea obiectelorgeometrice, de obicei de la stânga ladreapta.

Baleierea oferã o metodã pentruordonarea obiectelor geometrice, deobicei, plasându-le într-o structurãde date, pentru obþinerea relaþiilordintre ele.

De obicei, algoritmii de baleieregestioneazã douã mulþimi de date: • starea liniei de baleiere indicã rela-

þia dintre obiectele intersectate delinia de baleiere;

• lista punct-eveniment este o sec-venþã de coordonate x, ordonate dela stânga la dreapta de obicei, caredefinesc poziþiile de oprire aledreptei de baleiere; fiecare astfel depoziþie de oprire se numeºte puncteveniment; numai în punctele eve-niment se întâlnesc modificãri alestãrii liniei de baleiere.

Pentru unii algoritmi lista punct-eveniment este determinatã dinamicîn timpul execuþiei algoritmului.

SoluþieVom deplasa o dreaptã de baleiereverticalã, imaginarã, de la stânga ladreapta. Lista punct-eveniment vaconþine capetele segmentelor orizon-tale ºi tipul acestora (extremitatestângã sau extremitate dreaptã) ºisegmentele verticale.

Pe mãsurã ce ne deplasam de lastânga la dreapta, când întâlnim o ex-tremitate stângã o inserãm în stãriledreptei de baleiere, iar când întâlnimo extremitate dreaptã ºtergem extre-mitatea stângã corespunzãtoare dinstãrile dreptei de baleiere.

Când întâlnim un segment verti-cal, numãrul de intersecþii ale acestuisegment cu alte segmente orizontaleva fi dat de numãrul capetelor de in-tervale care se aflã în stãrile drepteide baleiere cuprinse între coordona-tele verticale ale extremitãþilor seg-mentului vertical.

Astfel, stãrile dreptei de baleieretrebuie sã fie reprezentate de o struc-

focusG

Info

nr. 1

5/4

- ap

rilie 2

005

37

turã de date pentru care avem nevoiede urmãtoarele operaþii:• Insereazã(y): insereazã extremitatea

y;• ªterge(y): ºterge extremitatea y;• Interogare(y1, y2) : determinã nu-

mãrul de extremitãþi cuprinse în in-tervalul [y1, y2]

Fie maxc valoarea maximã a coor-donatelor extremitãþilor de segmen-te. Folosind un vector pentru a im-plementa aceste operaþii vom obþineun ordin de complexitate O(1) pen-tru primele douã operaþii ºi O(maxc)pentru cea de-a treia.

Astfel, ordinul de complexitate alalgoritmului de rezolvare a proble-mei va fi O(N · maxc) în cazul celmai defavorabil.

Putem comprima spaþiul [0…maxc] observând cã doar maxim Nvalori din acest interval conteazã, ºianume extremitãþile segmentelor ori-zontale, astfel reducându-se ordinulde complexitate a celei de-a treia ope-raþii la O(N), dar algoritmul va aveaordinul de complexitate O(N2), ceeace nu aduce nici o îmbunãtãþire faþãde algoritmul trivial.

Aceastã situaþie ne determinã sãcãutãm o structurã de date mai efi-cientã. O primã variantã ar fi împãr-þirea vectorului în bucãþi de ele-mente, reducând astfel ordinul decomplexitate la O(N · ).

În continuare vom prezenta solu-þia bazatã pe arborii de intervale.

Vom folosi un arbore de inter-vale pentru a simula operaþiile, care

erau efectuate folosind un vector obiº-nuit, în timp logaritmic.

Astfel, în fiecare nod al arboreluidin intervale vom reþine câte extre-mitãþi existã în acel interval.

Primele douã operaþii vor fi im-plementate folosind procedura Ac-tualizare de mai sus pentru inter-valul [y, y] în arborele T(0, maxc) ºiadunând +1, respectiv -1 la fiecarenod actualizat.

Cea de-a treia operaþie poate firealizatã folosind funcþia Interoga-re pentru intervalul [y1, y2]. Astfel or-dinul de complexitate al algoritmuluise reduce la O(N · log maxc).

Folosind aceeaºi tehnicã de "com-primare" a coordonatelor se poateobþine ordinul de complexitate O(N· log N).

În figura 2 este prezentatã struc-tura arborelui de intervale, dupã ac-tualizarea pentru intervalele [2, 2],[6, 6] ºi [9, 9]. Sunt marcate interva-lele care conduc la obþinerea numã-rului de segmente intersectate de pri-mul segment vertical, obþinute în ur-ma interogãrii pentru intervalul [0, 8].

Problema #2(preluatã de la IOI '98 - Portugalia)

Se considera N ≤ 50.000 dreptun-ghiuri în plan, fiecare având laturileparalele cu axele Ox ºi Oy.

Lungimea marginilor (contururi-lor) reuniunii tuturor dreptunghiuri-lor se va numi perimetru.

Sã se calculeze perimetrul celorN dreptunghiuri.

În fiºierul drept.in se aflã peprima linie numãrul N al dreptun-

ghiurilor, iar pe fiecare dintre urmã-toarele N linii se aflã câte patru nu-mere naturale, mai mici decât 50.000,reprezentând coordonatele cartezie-ne ale colþurior stânga-sus, respectivdreapta-jos, ale fiecãrui dreptunghi.

Rezultatul va fi scris în fiºieruldrept.out.

Exempludrept.in

3

3 8 8 3

6 10 12 6

12 4 15 1

drept.out

44

Timp de execuþie: 1 secundã/test

SoluþieFolosind un raþionament asemãnãtorcelui utilizat în cazul primei proble-me, constatãm necesitatea unui algo-ritm de baleiere.

Vom descompune problema îndouã subprobleme: prima datã calcu-lãm perimetrul folosind doar laturilestânga ºi dreapta ale dreptunghiurilorpentru a calcula perimetrul pe axa Oy;iar apoi putem sã rotim dreptunghiu-rile ºi sã folosim acceaºi procedurãpentru a calcula perimetrul pe axaOx, folosind doar laturile sus ºi josale dreptunghiurilor.

Fiecare laturã (stângã sau dreap-tã) va fi un punct eveniment. Sortãmlaturile crescãtor în funcþie de coor-donata orizontalã ºi începem parcur-gerea de la stânga la dreapta.

În momentul în care întâlnim olaturã stângã marcãm în stãrile drep-tei de baleiere, intervalul de unitãþiocupat de laturã pe axa Oy, iar cândîntâlnim o laturã dreaptã demarcãm

N

N

FFiigguurraa 22:: AArrbboorree ddee iinntteerrvvaallee ppeennttrruu pprroobblleemmaa ##11

GIn

fo n

r. 1

5/4

- a

pri

lie 2

005

38

focu

sîn stãrile dreptei de baleiere interva-lul de unitãþi ocupat de laturã.

Între oricare douã puncte eveni-ment consecutive are loc o modifica-re a perimetrului total pe axa Oy.

Astfel, dupã fiecare actualizare astãrilor dreptei de baleiere se va reþi-ne numãrul de unitãþi marcate pânãîn prezent (nu se þine cont dacã o uni-tate este marcatã de mai multe ori).

De fiecare datã vom aduna la pe-rimetrul total pe axa Oy diferenþaabsolutã între numãrul de unitãþimarcate pânã în prezent ºi valoareaimediat anterioarã (înaintea actuali-zãrii) a numãrului de unitãþi marcate.

Aºadar, este necesarã o structurãde date care se efectueze urmãtoareleoperaþii în timp eficient:• Marcheazã(a, b): marcheazã inter-

valul [a, b];• Demarcheazã(a, b): demarcheazã

intervalul [a, b];• Interogare: returneazã numãrul to-

tal de coordonate marcate pânã înprezent

Putem utiliza un arbore de inter-vale pentru a obþine un ordin de com-plexitate O(log maxc) sau O(log N)pentru primele douã operaþii ºi O(1)pentru ce-a de treia.

În fiecare nod al arborelui reþi-nem de câte ori a fost marcat interva-lul respectiv ºi câte unitãþi din inter-valul respectiv au fost marcate.

Primele douã operaþii pot fi im-plementate folosind procedura Ac-tualizare, iar a treia operaþie va re-turna valoarea numãrului de unitãþicare au fost marcate din rãdãcina ar-borelui de intervale.

În figura 3 este descrisã structuraarborelui de intervale, dupã marcareaintervalelor [3...8] ºi [6...10] (un inter-val [y1…y2] reprezintã intervalul deunitãþi [y1, y2 - 1] din arbore).

Problema #3Se dau N ≤ 100.000 puncte în plan alecãror coordonate sunt numere natu-rale mai mici ca 2.000.000.000.

Sã se rãspundã la M ≤ 1.000.000întrebãri de forma "câte puncte din-tre cele N existã în dreptunghiul cucolþul stânga-sus în punctul de coor-donate (x1, y1) ºi colþul dreapta-jos înpunctul de coordonate (x2, y2)?"

În fiºierul puncte.in se vor aflape prima linie numerele N ºi M. Peurmãtoarele N linii se aflã coordona-tele punctelor. Pe urmãtoarele M li-nii se vor afla câte patru numere na-turale reprezentând coordonatelecolþurilor dreptunghiurilor.

În fiºierul puncte.out se vor aflaM numere naturale reprezentând rãs-punsurile la întrebãri.

Exemplupuncte.in

6 1

2 8

5 3

6 5

8 7

8 1

10 10

4 8 9 4

puncte.out

2

Timp de execuþie: 1 secundã/test

SoluþieProblema determinãrii numãrului depuncte din interiorul unui dreptunghieste o particularizare 2D pentru pro-blema numitã în literatura de specia-litate Orthogonal Range Search.

Varianta aleasã pentru acest caz,constã într-un arbore de intervale, ca-re permite determinarea numãruluide puncte din interiorul unui drept-unghi folosind un algoritm cu ordi-nul de complexitate O(log2 N).

Astfel, se sorteazã coordonatele xale punctelor ºi se construieºte un ar-bore de intervale. Primul nivel al ar-borelui va conþine toate coordonatelex.

Cei doi fii ai rãdãcinii vor conþi-ne prima jumãtate, respectiv a douajumãtate a punctelor (sortate în func-þie de coordonata x) º.a.m.d. Pentrufiecare interval de coordonate x, semenþin sortate coordonatele y cores-punzãtoare punctelor care au coor-donatele x în intervalul respectiv.Astfel, memoria folositã are ordinulO(N · log N).

Pentru a construi efectiv se folo-seºte o abordare asemãnãtoare algo-ritmului de sortare prin interclasare:în fiecare nod, pentru a obþine listade coordonate y ordonate, se inter-claseazã listele celor doi fii (deja or-donate). Când se ajunge într-o frun-zã, lista nodului este formatã dintr-unsingur punct.

Pentru fiecare dreptunghi, se efec-tueazã cãutarea în arborele de inter-vale pentru segmentul [x1, x2] (deoa-rece se folosesc doar cele N coordo-nate x ale punctelor, se vor potrivicapetele acestui interval folosindcãutarea binarã la cea mai apropiatãcoordonatã x de fiecare extremitate). FFiigguurraa 33:: AArrbboorree ddee iinntteerrvvaallee ppeennttrruu pprroobblleemmaa ##22

focusG

Info

nr. 1

5/4

- ap

rilie 2

005

39

Pentru fiecare interval din arboreatins, se executã douã cãutãri binareprintre coordonatele y corespunzã-toare coordonatelor x din acel inter-val, pentru a determina câte punctedin intervalul respectiv se aflã în in-tervalul [y1, y2] (adicã în interioruldreptunghiului).

Structura arborelui de intervaleutilizat este prezentatã în figura 4.

Ordinul de complexitate O(log2

N) poate fi redus, folosind o metodãdescoperitã independent de Willardºi Lueker în anul 1978. Se observã cãpentru fiecare coordonatã y dintr-unnod, dacã presupunem cã se efectuea-zã o cãutare binarã, atunci putem de-termina în timpul interclasãrii poziþiadin fiecare fiu pe care o va returna cã-utarea binarã pentru aceeaºi valoare.

Este evident cã pentru o valoarey dintr-un nod, care a provenit din-tr-un fiu în timpul interclasãrii, exis-tã o unicã valoare maximã y' dincelãlalt fiu astfel încât y' ≤ y. Aºadar,pãstrãm pentru fiecare valoare y din-tr-un nod doi indici care identificã

poziþiile corespunzãtoa-re efectuãrii unei cãutãribinare în fii pentru va-loarea y.

Astfel, în timpul cã-utãrii, în loc sã efectuãmcãutãri binare, se pot par-curge aceºti indici careoferã în timp constantpoziþia în lista cãutatã,reducând ordinul decomplexitate la O(logN). Procedeul este ilus-trat în figura 5.

Probleme propusePrezentãm în cele ce urmeazã enun-þurile a patru probleme care pot fi re-zolvate folosind arborii de intervale.

Problema #4Olimpiada Balticã de Informaticã, 2001

Se considerã N ≤ 50.000 dreptunghiuriîn plan, fiecare având laturile paralelecu axele Ox ºi Oy. Sã se determinearia ocupatã de reuniunea celor Ndreptunghiuri.

În fiºierul drept2.in se aflã peprima linie numãrul N al dreptun-ghiurilor, iar pe fiecare dintre urmã-toarele N linii se aflã câte patru nu-mere naturale mai mici decât 50.000,reprezentând coordonatele cartezie-ne ale colþului stânga-sus, respectivdreapta-jos ale fiecãrui dreptunghi.

Rezultatul se va scrie în fiºieruldrept2.out.

Problema #5Olimpiada Naþionalã de Informaticã,

Polonia, 2001

Se considerã N ≤ 50.000puncte care au coordo-nate numere naturalemai mici decât 50.000.Sã se determine poziþiaîn care se poate aºezaun dreptunghi de lun-gime DX ºi lãþime DY,astfel încât numãrul depuncte incluse în drept-unghi sã fie maxim.

În fiºierulpuncte2.in se aflã peprima linie numerele N,DX ºi DY. Pe urmãtoa-

rele N linii se aflã coordonatele punc-telor.

În fiºierul puncte2.out se vor gã-si cinci numere naturale reprezentândcoordonatele colþurilor stânga-sus ºidreapta-jos ale aºezãrii dreptunghiu-lui ºi numãrul maxim de puncte dindreptunghi.

Problema #6Baraj pentru lotul naþional, 2003

Se considerã N ≤ 100.000 puncte careau coordonate numere naturale maimici ca 100.000. Sã se determine un-de se pot aºeza douã dreptunghiuride lungime DX ºi lãþime DY, fãrã sãse intersecteze, astfel încât numãrulde puncte incluse în cele douã drept-unghiuri sã fie maxim.

În fiºierul puncte3.in se aflã peprima linie numerele N, DX ºi DY.Pe urmãtoarele N linii se aflã coor-donatele punctelor.

În fiºierul puncte3.out se vorafla nouã numere naturale reprezen-tând coordonatele colþurilor din stân-ga-sus ºi dreapta-jos ale celor douãdreptunghiuri, precum ºi numãrulmaxim de puncte incluse în acestea.

Problema #7USACO, ianuarie 2004

Se considerã N ≤ 250.000 dreptun-ghiuri în plan, fiecare având laturileparalele cu axele Ox ºi Oy, care nuse intersecteazã ºi nu se ating, darpot fi incluse unul în altul. Se nu-meºte închisoare un dreptunghi în-conjurat de alte dreptunghiuri. Sã sedetermine numãrul maxim de drept-unghiuri de care poate fi înconjuratão închisoare ºi câte astfel de închisorimaxime existã.

În fiºierul inchis.in se aflã peprima linie numãrul N al dreptun-ghiurilor, iar pe fiecare din urmãtoa-rele N linii se aflã câte patru numerenaturale mai mici decât 1.000.000.000,reprezentând coordonatele cartezie-ne ale colþului stânga-sus, respectivdreapta-jos ale fiecãrui dreptunghi.

În fiºierul inchis.out se vorafla douã numere naturale: numãrulmaxim de dreptunghiuri de care poa-te fi înconjuratã o închisoare ºi nu-mãrul acestor "închisori" maxime.

FFiigguurraa 44:: AArrbboorree ddee iinntteerrvvaallee ppeennttrruu pprroobblleemmaa ##33

FFiigguurraa 55:: RReedduucceerreeaa ccoommpplleexxiittăăţţiiii ppeennttrruu pprroobblleemmaa ##33