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 înainte 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 într-un mod ingenios. 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#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.

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

p=. _Numărul maxim de elemente ce pot trece prin deque este $8$. Arborele ţine evidenţa intervalului $[3, 6]$._

p=. _Numărul maxim de elemente ce pot trece prin deque este $8$. Arborele ţine evidenţa elementelor $3$, $4$, $5$, $6$._

Algoritmul în pseudocod arată în felul următor:
== code(cpp) |
Algoritmul este:

    // S[] şirul iniţial de numere iar N lungimea sa
    // (last, i] este intervalul de lungime maximă care se termină în i a cărui sumă nu depăşeşte M

    sum  = 0;
    last = 0;
    // indicii head si tail ai dequeului