Cu ajutorul relaţiei <tex> (*) </tex> şi a şirului <tex> j_{1} < j_{2} < .. < j_{K} = i </tex> vom construi un alt vector <tex> iMin </tex> cu proprietatea că <tex> iMin_{p} = Min\{bst_{r} + S_{j_{p}} : j_{p-1} \le r < j_{p}\} </tex>. În final, <tex> bst_{i} = Minim\{iMin_{1}, iMin_{2}, .., iMin_{K}\} </tex>, rezultat pe care îl putem obţine în <tex> O(log_{2}N) </tex> dacă folosim un arbore de intervale.
Însă, cum se construieşte şirul <tex> j_{1} < j_{2} < .. < j_{K} = i </tex>? În 'a doua problemă':deque-si-aplicatii#problema-2 am construit cu ajutorul unui deque exact şirul de indici de care avem nevoie aici. Când vom înainta la indicele <tex> i + 1 </tex> vom modifica şirul astfel încât să respecte proprietăţile de mai sus utilizând operaţiile normale asupra unui deque. Mai sus am menţionat cum se obţine <tex> bst_{i} </tex> lucru care implică combinarea structurilor de deque şi arbore de intervale. Arborele de intervale reţine valorile lui <tex> iMin </tex> pentru fiecare element al dequelui. Mai jos se vede o figură în care elementele unui deque sunt defapt o secvenţă „continuă” de frunze ale unui arbore de intervale.
Însă, cum se construieşte şirul <tex> j_{1} < j_{2} < .. < j_{K} = i </tex>? În 'a doua problemă':deque-si-aplicatii#problema-2 am construit cu ajutorul unui deque exact şirul de indici de care avem nevoie aici. Când vom înainta la indicele <tex> i + 1 </tex> vom modifica şirul astfel încât să respecte proprietăţile de mai sus utilizând operaţiile normale asupra unui deque. Mai sus am menţionat cum se obţine <tex> bst_{i} </tex> lucru care implică combinarea structurilor de deque şi arbore de intervale. Arborele de intervale reţine valorile lui <tex> iMin </tex> pentru fiecare element al dequelui.
p=. !deque-si-aplicatii?PKU.png 60%!
Pentru a înţelege cum funcţionează acest algoritm să considerăm ca date de intrare şirul <tex> S = \{5, 9, 4, 7, 4, 1, 6, 3\} </tex> şi <tex> M = 15 </tex>. Perechile din deque sunt de forma <tex> (S_{i}, iMin_{p}) </tex>. Fie <tex> i = 1, 2, \ldots 8 </tex>:
p=. _Numărul maxim de elemente ce pot trece prin deque este $8$. În figură, arborele ţine evidenţa elementelor $3$, $4$, $5$, $6$ din deque._
* <tex> i = 1: j = 0, head = 1, tail = 1, deque = \{\ (5, 0)\ \} \Rightarrow bst_{1} = 5; </tex>
* <tex> i = 2: j = 0, head = 1, tail = 1, deque = \{\ (9, 0)\ \} \Rightarrow bst_{2} = 9; </tex>
* <tex> i = 3: j = 1, head = 1, tail = 2, deque = \{\ (9, 5),\ (4, 9)\ \} \Rightarrow bst_{3} = 13; </tex>
* <tex> i = 4: j = 2, head = 2, tail = 2, deque = \{\ (7, 9)\ \} \Rightarrow bst_{4} = 16; </tex>
* <tex> i = 5: j = 2, head = 2, tail = 3, deque = \{\ (7, 9),\ (4, 16)\ \} \Rightarrow bst_{5} = 16; </tex>
* <tex> i = 6: j = 3, head = 2, tail = 4, deque = \{\ (7, 13),\ (4, 16),\ (1, 16)\ \} \Rightarrow bst_{6} = 17; </tex>
* <tex> i = 7: j = 4, head = 3, tail = 3, deque = \{\ (6, 16)\ \} \Rightarrow bst_{7} = 22; </tex>
* <tex> i = 8: j = 4, head = 3, tail = 4, deque = \{\ (6, 16),\ (3, 22)\ \} \Rightarrow bst_{8} = 22; </tex>
Mai jos se vede o figură în care elementele unui deque sunt defapt o secvenţă „continuă” de frunze ale unui arbore de intervale pentru cazul <tex> i = 6 </tex>.
p=. !deque-si-aplicatii?PKU0.png 60%!
p=. _Numărul maxim de elemente ce pot trece prin deque este $8$. În figură, arborele ţine minimul de pe poziţiile $2$, $3$, $4$ din deque._
Algoritmul în pseudocod arată în felul următor:
