după care rezolvăm problema pentru sufix şi prefix prin metoda liniară în $O(N/K)$, şi determinăm în $O(1)$ pentru fiecare bucată în care este spart şirul $a[x..y]$ subsecvenţa ei de sumă maximă.

Mai rămâne să găsim subsecvenţa de sumă maximă cu capătul în bucăţi diferite. Pentru două bucăţi fixate $i < j$, subsecvenţa de sumă maximă ce are câte un capăt în fiecare bucată are valoarea: $max[j] - min[i]$. Determinarea subsecvenţei de sumă maximă cu capetele în bucăţi diferite devine astfel de complexitate $O(K)$. Deci, pentru a rezolva o întrebare trebuie să facem $O(N/K + K)$ calcule. Pentru a reduce complexitatea problemei considerăm pe $K = sqrt(N)$. Complexitatea totală a acestei soluţii este $O(N + M sqrt(N))$.

Mai rămâne să găsim subsecvenţa de sumă maximă cu capătul în bucăţi diferite. Pentru două bucăţi fixate $i < j$, subsecvenţa de sumă maximă ce are câte un capăt în fiecare bucată are valoarea: $max[j] - min[i]$. Determinarea subsecvenţei de sumă maximă cu capetele în bucăţi diferite devine astfel de complexitate $O(K)$. Deci, pentru a rezolva o întrebare trebuie să facem $O(N/K + K)$ calcule. Pentru a reduce complexitatea problemei considerăm pe $K = sqrt(N)$. Complexitatea totală a acestei soluţii este $O(N + M*sqrt(N))$.

Să vedem ce se întâmplă pe exemplu:

* $best[x..y] = maxim(best[x..(x+y)/2], maxim(best[(x+y)/2 + 1 .. y], max[(x+y)/2 + 1 .. y] - min[x..(x+y)/2]))$.

Acum pentru a răspunde la întrebările din problemă fiecare interval va fi împărţit în $O(log N)$ subintervale canonice care apar în arborele de intervale. Apoi printr-o parcurgere asemănătoare celei din rezolvarea anterioară se poate obţine rezultatul pentru fiecare întrebare în $O(log N)$. Soluţia va avea complexitatea $O(N + M log N)$.

Acum pentru a răspunde la întrebările din problemă fiecare interval va fi împărţit în $O(log N)$ subintervale canonice care apar în arborele de intervale. Apoi printr-o parcurgere asemănătoare celei din rezolvarea anterioară se poate obţine rezultatul pentru fiecare întrebare în $O(log N)$. Soluţia va avea complexitatea $O(N + M * log N)$.

În următorul desen observăm structura unui arbore de intervale pentru un şir cu $16$ elemente. Daca se pune întrebarea $[2, 11]$ acest interval va fi spart în intervalele $[2, 2], [3, 4], [5, 8], [9, 10], [11, 11]$.