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#problema2 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. Mai jos se vede o figură în care elementele unui deque sunt defapt o secvenţă „continuă” de frunze ale unui arbore de intervale.

p=. !deque-si-aplicatii?PKU.png 60%!