Subiectul acestui post nu este nou, dar, sigur, cineva va veni la îndemână. Să începem cu un exemplu de problemă în care se utilizează un arbore de segmente.
Există o serie de numere întregi n (n≤10 ^ 5), trebuie să găsiți suma pe segment de la l la r (0≤l, r≤n-1) și să modificați valoarea i-ei
(0≤i≤n-1) a elementului. Numărul de cereri m (m≤10 ^ 5).
Evident, soluția naivă funcționează pentru O (n * m), iar arborele segmentelor face posibilă rezolvarea problemei date cu asimptotica O (m * log2n).
Există multe tipuri diferite de segmente de copaci. În acest articol, arborele segmentelor este o structură de date care poate efectua rapid două tipuri de interogări (în timp logaritmic) în funcție de secvența disponibilă a numerelor n:
1) Schimbați valoarea elementului i
2) Calculați valoarea unei anumite funcții asociative fixe pe segmentul de la l la r.
Care este arborele de segmente (DO)? Pentru a - arbore binar (de obicei, pentru comoditatea complement pentru a finaliza cu zero elemente), care sunt frunze ale elementelor de matrice sursă și fiecare vârf valoarea funcției f înregistrată în doi fii. Aceasta este, în foi înregistrate funcție de valoare pe durata intervalului 1, se înregistrează în valoarea de bază a funcției la intervalul de lungime 2, în care părintele - 4 ... astfel înregistrată la fiecare valoare vârf al funcției de la un anumit interval de timp care a fost motivul pentru acest nume.
Pentru sarcina noastră de exemplu, funcția f este suma, atunci DO pentru cele patru elemente va arăta astfel:
Dacă avem numărul de elemente (n) nu este o putere de două, atunci le vom adăuga cu zerouri. , De exemplu, pentru a rezuma 3 elemente ar fi - (în general, atunci când lucrăm cu tipul de date T și o funcție f, scorul o valoare astfel încât pentru orice x f dreapta T (x, zero) = x.):
Cum se stochează TO? Există 2 moduri:
• structuri pe indicatoare;
• Matricea liniară.
Din câte știu, prima metodă este folosită numai pentru UP. Încă analizăm modificarea cea mai comună și mai simplă a DO, așa că vom folosi a doua metodă. Creați o matrice liniară a elementelor 2 * nMax, unde nMax este cea mai mică putere de două care nu depășește n. Primul element (a [1]) va stoca rădăcina arborelui, și pentru fiecare nod i din fiii săi stocate în celule numerotate de 2 * i (fiu din stânga) 2 * i + 1 (fiu dreapta). De ce există suficiente elemente 2 * nMax pentru stocare? Avem foi nmax, ei nMAX / 2 părinți, ei nMAX / 4 ... și 1 rădăcină, este clar că această sumă (1 + 2 + 4 + ... + nMAX / 4 + nMAX / 2 + Nmax) este egal cu 2 * Nmax -1.
În figură, să plasăm indexul în matricele de lângă fiecare vârf:
Și arborele va fi așezat în matrice după cum urmează:
Acum, să definim ce operațiuni vrem să realizăm cu DO:
1) pentru a construi un DO;
2) afla valoarea elementului i;
3) modificați valoarea elementului i;
4) găsiți valoarea funcției pe segment de la l la r.
Vom analiza toate operațiunile la rândul lor.
1 Construiți un arbore al segmentelor.
Să presupunem că avem o matrice b de elemente n. În primul rând, trebuie să găsim nMax (cea mai mică putere de două care nu depășește n). Acest lucru se poate realiza fie prin formula:
și un ciclu simplu:
În plus, necesitatea de a umple matrice cu zerouri (de tip corespunzător) și umple foile cu valorile din matrice b (ne amintim că indicii de frunze la Nmax la 2 * Nmax-1):
În momentul de față avem:
Acum rămâne doar să umplem valorile în toți părinții. Acest lucru poate fi realizat într-un singur pasaj liniar (amintiți-vă că i-lea fii vertex cu indici 2 * i și 2 * i + 1, iar vârful stocăm valoarea unei funcții a doi fii):
Astfel, am construit un DO cu asimptotica O (nMax) = O (n).
2 Gasiti valoarea elementului i.
După cum sa menționat deja anterior în frunze noastre de a avea indici de la Nmax la 2 * Nmax-1, astfel încât valoarea elementului i-lea al elementului să fie în celula cu un indice de nMAX + i: returnează un [Vmax + i] Este evident că interogarea este executată pentru constanta .
3 Modificați valoarea elementului i.
Dacă vom schimba valoarea din foaia arborelui, atunci toate valorile din calea spre rădăcină din această foaie vor înceta să corespundă realității, deci trebuie să fie recalculate, în rest rămân valorile corecte. După cum știți, adâncimea unui arbore binar complet de vârfuri m este log2m, deci trebuie să efectuăm această operație într-un timp logaritmic. De exemplu, modificați a2 la a2 I:
Roșu evidențiază nodurile în care doriți să modificați valorile.
Pentru a "actualiza" BD, trebuie să scrie o nouă valoare în foaie și apoi să mergem până la rădăcină, de fiecare dată când recalculează valoarea funcției la vârf. Schimbarea valorii în foaie este foarte simplă (rețineți că indicii frunzelor sunt de la nMax la 2 * nMax-1). Valoarea tabelului i are indicele nMax + i:
Acum rămâne să urcați la rădăcină, acest lucru se poate face cu o buclă:
4 Gasiti valoarea functiei pe segment de la l la r.
În cele din urmă, am ajuns la cea mai interesantă cerere. Este de remarcat faptul că cazul special atunci când l = r este analizat în clauza 2 și este satisfăcut ca o constantă, în cazul general, asimptotica este logaritmică.
Segmentul fundamental este un segment pentru care există un vârf în arborele care stochează valoarea funcției pe un anumit interval.
Nivelul. Nivelul rădăcinii este 1, iar pentru fiecare fiu nivelul este unul mai mare decât cel al părintelui.
Pentru a calcula valoarea unei funcții pe un segment, trebuie să o defalcăm în numărul minim de segmente fundamentale. Pentru a găsi valoarea pentru orice vertex (cu excepția foii), trebuie să cunoaștem semnificațiile pentru fii. Vom coborî pe DO. Inițial, ridică-te în rădăcină. Să fim la un vârf. Luați în considerare cele 3 cazuri posibile: segmentul [l..r] coincide cu segmentul corespunzător vertex curent, segmentul [l..r] aparține în totalitate unuia dintre copii, segmentul aparține ambelor fii. În primul caz, returnează doar valoarea numărului de UP, în al doilea - în jos la acest fiu, vom împărți acest segment în două-trei în același eveniment: [l..pravy sfârșitul fiului din stânga] și [capătul din stânga syna..r dreapta]. Calculați recursiv valorile pentru fiecare dintre ele.
Luați în considerare exemplul. Să presupunem că avem DO pentru 8 elemente, scrieți ce segment corespunde fiecărui vârf:
Și acum, să vedem cum va fi executată interogarea segmentului [1..5].
Mai întâi ne ridicăm la rădăcină - segmentul nostru aparține ambilor fii. Prin urmare, trebuie să o rupem în două segmente: [1..3] și [4..5]. Pentru fiecare dintre ele, calculează recursiv valoarea. Mai departe, segmentul [1..3] aparține din nou celor 2 fii, îi împărțim în 2 segmente: [1..1] și [2..3]. Segmentul [1..1] aparține numai fiului potrivit, mergem în jos și vedem că segmentul [1..1] este fundamental. Luăm pentru el valoarea de la vârf și se ridică la 2 nivele (vertex [0..3]). Pentru fiul stâng am numărați recursiv, acum numărăm dreptatea: mergem în jos. Segmentul [2..3] este fundamental, luăm valoarea de la vârf. Vom reveni la [0..3] și putem calcula valoarea pentru intervalul [1..3], deoarece valoarea funcției a fost deja calculată pentru ambele părți. Ne întoarcem la rădăcină și mergem la fiul potrivit [4..7], sub-secțiunea noastră ([4..5]) aparține unui singur fiu stâng, intră în el. Vârful corespunde segmentului [4..5], deci este unul fundamental, luăm valoarea de la vârf. Ne intoarcem la radacina si calculam raspunsul.
De ce se execută această solicitare într-un timp logaritmic? După cum se știe, adâncimea (numărul de nivele) al arborelui de n noduri este egal cu log2, în plus, se precizează că, la fiecare nivel vom vizita la 4 vârfuri, deci vizităm O (log2) noduri. Luați în considerare codul. Pentru a calcula valoarea segmentului, avem nevoie de o recursive argumente apel funcția de 5, pentru comoditate ne scrie că funcția 2 argumente (interogarea pentru limite segment) este de 5 argumente și o funcție și returnează valoarea:
Acum, funcția noastră recursivă:
Codul meu pentru segmentele arborelui de clasă este o singură modificare.
P.S. Voi fi fericit cu comentarii / sugestii constructive pentru scrierea unui articol / cod
segmente de copaci. poze. cod. segment arbore
Trimiteți-le prietenilor: