Arborele segmentului

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 6 octombrie 2016; verificarea necesită 41 de modificări .

Un arbore de segment este o structură de date care vă permite să găsiți valoarea unei funcții asociative pe un segment arbitrar al unui tablou pentru asimptotice . Cele mai frecvent utilizate funcții sunt suma, produsul, maximum și minim.

Descrierea structurii

Arborele segment este un arbore înrădăcinat, ale cărui frunze sunt elementele tabloului original, iar celelalte vârfuri au câte 2 copii. Fiecărui vârf i se atribuie un interval care este uniunea intervalelor copiilor săi (dacă vârful are copii), sau un interval care conține un element specific al tabloului (pentru frunze). În plus, pentru fiecare vârf este stocată valoarea unei funcții asociative dintr-un interval dat. Acest arbore va avea o înălțime logaritmică deoarece numărul de niveluri nu va depăși

Arborele de segmente în memorie

Fie ca tabloul nostru să aibă elemente: .

Să alegem astfel încât . Să completăm matricea noastră din dreapta cu elemente neutre, astfel încât lungimea sa să fie egală cu . Apoi, pentru a stoca arborele de segment construit pe elementele matricei , avem nevoie de o matrice de celule.

Nu vom folosi celula zero din matrice , iar celulele de la prima la -a vor corespunde vârfurilor arborelui binar cu numerele corespunzătoare. De obicei, numerotarea vârfurilor arborelui segment este folosită în ordinea parcurgerii în lățime , adică rădăcina arborelui are numărul 1, iar fiii din stânga și din dreapta vârfului cu numărul au numere și respectiv. Cu această numerotare, vârful cu numărul la va corespunde segmentului , adică numărul va fi stocat în celulă .


În continuare în articol, se va folosi această numerotare a vârfurilor arborelui de segmente. Ca alternativă, puteți numerota vârfurile în ordinea traversării adâncimii , apoi fiii din stânga și din dreapta nodului vor avea numere și , unde este segmentul corespunzător vârfului . În același timp, dacă construiți imediat un arbore de segment în conformitate cu matricea originală și nu îl extindeți la o lungime (într-un astfel de arbore, nu toate lungimile segmentelor vor fi puteri de două și nu toate frunzele vor fi situate la maximum adâncime), atunci toate celulele din matrice vor fi suficiente pentru a-l stoca . La stocarea unui arbore, ale cărui vârfuri sunt numerotate în ordinea traversării în lățime, lungimea matricei poate ajunge la .

Construirea unui arbore de segmente

Mai jos este codul C++ pentru o funcție recursivă pentru construirea unui arbore de segmente pentru o sumă pe elementele unui tablou . Complexitatea construirii unui copac este acțiunile.

void build() { build(1, 0, (1 << h) - 1); } void build (int v, int L, int R) { dacă (L == R){ b[v] = a[L]; } else { int C = (L + R) / 2; construi (v * 2, L, C); construi (v * 2 + 1, C + 1, R); b[v] = b[v * 2] + b[v * 2 + 1]; } }

Arborele de segmente cu o singură modificare

Schimbarea elementului

Să schimbăm valoarea lui . Apoi trebuie să actualizăm valorile din celulele , , ,..., . Astfel, va lua măsuri pentru a schimba elementul.

Mai jos este codul C++ pentru o procedură recursivă pentru actualizarea arborelui de segmente pentru suma atunci când elementul --lea din tabloul sursă se modifică .

void update(int i, int newValue) { update(1, 0, (1 << h) - 1, i, newValue); } void update (int v, int L, int R, int i, int newValue) { dacă (L == R){ b[v] = newValue; a[i] = newValue; } else { int C = (L + R) / 2; dacă (i <= C){ actualizare(v * 2, L, C, i, newValue); } else { actualizare(v * 2 + 1, C + 1, R, i, newValue); } b[v] = b[v * 2] + b[v * 2 + 1]; } }

Calcularea unei funcții pentru un segment

Pentru a calcula o funcție din elemente , se folosește următoarea funcție recursivă din argumente , care calculează valoarea funcției pentru segment . Aici este un astfel de vârf de arbore încât celula conține valoarea funcției pentru segment .

Dacă segmentele și nu se intersectează, atunci răspunsul este egal cu elementul neutru pentru funcție (0 pentru sumă, 1 pentru produs, pentru maxim, pentru minim).

Dacă , atunci răspunsul este .

În caz contrar, împărțim segmentul în jumătate setând . Să reducem problema la calcularea unei funcții pentru segmentele și . Atunci răspunsul este .

Astfel, calculul unei funcții pe un segment se reduce la calculul unei funcții din elementele matricei corespunzătoare unor segmente .

Să arătăm că atunci când funcția este calculată, rezultatele vor fi obținute. La fiecare adâncime, vom returna o valoare de la cel mult două vârfuri de arbore. Dimpotrivă, presupunem că sunt cel puțin trei dintre ele. Dar apoi două apeluri de la două vârfuri învecinate ar putea fi înlocuite cu un apel de la părintele lor comun. Prin urmare, la fiecare adâncime, nu vom returna mai mult de două valori. Datorită construcției, înălțimea copacului nu depășește . Prin urmare, nu se vor mai face returnări.

Raționament similar arată că într-o interogare din arbore nu vom ocoli nu mai mult de vârfuri.

Mai jos este codul C++ pentru calcularea sumei pe un segment .

int getSum(int l, int r) { return getSum(1, 0, (1 << h) - 1, l, r); } int getSum(int v, int L, int R, int l, int r) { dacă (L > r || R < l){ întoarce 0; } dacă (l <= L && R <= r){ întoarcere b[v]; } int C = (L + R) / 2; returnează getSum(v * 2, L, C, l, r) + getSum(v * 2 + 1, C + 1, R, l, r); }

Arborele de segmente cu modificarea intervalului

Să presupunem că dorim să modificăm nu valoarea unei celule a matricei , ci a întregului interval (de exemplu, creșteți valorile tuturor celulelor din interval cu un număr dat ). Atunci stocarea numai a matricei nu este suficientă. Cu toate acestea, arbori de segment capabili să calculeze suma și maximul pot fi implementați prin stocarea a două matrice de aceeași lungime și implementarea recursiv a operației de modificare.

Arborele de segmente pentru suma (RSQ)

Vom stoca matrice cu aceeași adresare ca și matrice (vezi mai sus).


Procedura recursivă va consta în creșterea valorii tuturor elementelor de pe segment cu numărul . poate fi atât pozitiv, cât și negativ. Aici este un vârf de arbore astfel încât celula să conţină suma tuturor elementelor din interval .

Mai jos este codul de procedură în C++.

void modificare (int l, int r, int X) { modifică (1, 0, (1 << h) - 1, l, r, X); } void modificare (int v, int L, int R, int l, int r, int X) { dacă (L > r || R < l){ întoarcere; } dacă (l <= L && R <= r){ suma[v] += X * (R - L + 1); adaugă[v] += X; } else { int C = (L + R) / 2; modifică (v * 2, L, C, l, r, X); modifică (v * 2 + 1, C + 1, R, l, r, X); sumă[v] = sumă[v * 2] + sumă[v * 2 + 1] + adăuga[v] * (R - L + 1); } }

Funcția recursivă pentru calcularea sumei pe un segment este modificată după cum urmează. Ea mai are un argument care caracterizează cât de mult aveți nevoie pentru a crește toate numerele de pe segment atunci când calculați suma.

int getSum(int l, int r) { return getSum(1, 0, (1 << h) - 1, l, r, 0); } int getSum(int v, int L, int R, int l, int r, int aditiv) { dacă (L > r || R < l){ întoarce 0; } dacă (l <= L && R <= r){ returnare suma[v] + aditiv * (R - L + 1); } int C = (L + R) / 2; returnează getSum(v * 2, L, C, l, r, aditiv + adaugă[v]) + getSum(v * 2 + 1, C + 1, R, l, r, aditiv + adaugă[v]); }


Complexitatea operațiunilor este de .

Arborele maxim de segmente (RMQ)

Similar cu cazul precedent, vom stoca matrice și . Procedura va avea același sens și aceleași argumente.

void modificare (int l, int r, int X) { modifică (1, 0, (1 << h) - 1, l, r, X); } void modificare (int v, int L, int R, int l, int r, int X) { dacă (L > r || R < l){ întoarcere; } dacă (l <= L && R <= r){ max[v] += X; adaugă[v] += X; } else { int C = (L + R) / 2; modifică (v * 2, L, C, l, r, X); modifică (v * 2 + 1, C + 1, R, l, r, X); max[v] = std::max(max[v * 2], max[v * 2 + 1]) + adăugare[v]; } }

Funcția recursivă pentru calcularea maximului pe un segment este implementată în mod similar cu funcția de arbore de segmente pentru sumă.

int getMax(int ​​​​l, int r) { return getMax(1, 0, (1 << h) - 1, l, r, 0); } int getMax (int ​​v, int L, int R, int l, int r, int aditiv) { dacă (L > r || R < l){ returnează -INF; // Minus infinit, i.e. un număr care este cu siguranță mai mic decât orice numere de pe segmentul nostru. De exemplu, dacă toate numerele sunt nenegative, atunci puteți pune INF = 0. } dacă (l <= L && R <= r){ return max[v] + aditiv; } int C = (L + R) / 2; int max1 = getMax(v * 2, L, C, l, r, aditiv + add[v]); int max2 = getMax(v * 2 + 1, C + 1, R, l, r, aditiv + add[v]); return std::max(max1, max2); }


Complexitatea operațiunilor este de .

Rezolvarea RMQ cu Sparse Table

De asemenea, problema RMQ poate fi rezolvată folosind Sparse table. Această structură de date vă permite să găsiți maximul/minimul pe segment în O(1) cu preprocesare în timp O(n log n).

Preprocesare:

Se notează - maxim / minim pe segmentul de la până la . O matrice poate fi completată dinamic astfel:

1) ;

2) sau respectiv.

Calcul:

Răspunsul la interval este (respectiv ), unde lg este puterea maximă a doi care nu depășește .

Exemplu:

Considerăm intervalul de la 1 la 5. Puterea maximă a doi care se potrivește pe el este de două, dar nu acoperă întregul interval, ci doar o parte de la 1 la 4. Maximul pe acest segment poate fi obținut prin compararea valorilor ​​de f[1,2] și f[2,2] (maxime pe segmentele de la 1 la 4 și de la 2 la 5).

Soluție O(1) cu preprocesare și memorie O(N)

Pentru o astfel de soluție, este suficient să reducem problema RMQ la problema LCA prin construirea unui arbore cartezian din elemente de forma , adică - cheie, - prioritate. Prioritățile trebuie ordonate de jos în sus, adică elementul cu cel mai mic . Evident, un astfel de arbore este ușor de construit pentru , deoarece toate cheile pe care le avem sunt ordonate (acestea sunt indici consecutivi ai elementelor matricei).

După aceea, răspunsul la orice solicitare va fi LCA a două vârfuri și . Indicele LCA va fi în , deoarece arborele cartezian prin cheie este un arbore binar. Datorită faptului că arborele cartezian este un heap prioritar , același nod va avea cea mai mică prioritate (valoarea elementului) dintre toate cele din

Sunt cunoscute mai multe soluții posibile pentru problema LCA cu preprocesare și memorie . O astfel de soluție este optimă asimptotic.

Link -uri

Vezi și