Putem folosi trucul construirii sumelor partiale prezentat in rezolvarea anterioara, pentru cazul *2D*. Pastram in $sum[i][j]$ suma tuturor elementelor $a[i{~1~}][j{~1~}]$ cu proprietatea ca $1 <= i{~1~} <= i$, si $1 <= j{~1~} <= j$. Putem calcula sumele prin metoda programarii dinamice (complexitate $O(N^2^)$) folosind formula $sum[i][j] = a[i][j] + sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1]$. Acum pentru a calcula suma elementelor din matricea cu colturile $(i{~1~}, j{~1~}), (i{~2~}, j{~2~})$, unde $i{~1~} <= i{~2~} si j{~1~} <= j{~2~}$ este suficient sa facem calculul $sum[i{~2~}][j{~2~}] - sum[i{~1~}-1][j{~2~}] - sum[i{~2~}][j{~1~}-1] + sum[i{~1~}-1][j{~1~}-1]$. Astfel putem evalua suma din fiecare submatrice in timp constant, deci rezolvarea are ordinul de complexitate $O(N^4^)$.
O alta idee ar fi ca pentru fiecare pereche $(i{~1~}, i{~2~})$ fixate sa determinam perechea optima $(j{~1~}, j{~2~})$. Daca avem liniile $i{~1~}$ si $i{~2~}$ fixate atunci problema se transforma din una bidimensionala in una unidimensionala. Astfel pentru fiecare coloana $j$ vom considera $b[j]$ ca suma a elementelor $a[i][j]$ cu proprietatea ca $i{~1~} <= i <= i{~2~}$. In exemplul nostru daca $i{~1~} = 2$ si $i{~2~} = 3$, atunci avem $b{~1~} = 9 + (-4)$, $b{~2~} = 2 + 1$, $b{~3~} = (-6) + (-4)$ si $b{~4~} = 2 + 1$. Pentru a rezolva problema unidimensionala folosim unul din algoritmii liniari prezentati mai sus, astfel obtinandu-se un algoritm de complexitate totala $O(N^3^)$. Acest truc de a fixa doua linii pentru a transforma problema in una unidimensionala este util in multe probleme pe matrice sau cu puncte in plan.
Cel mai bun algoritm cunoscut pentru aceasta problema are complexitatea <tex>O(N^{3((\log \log N)/\log N)^{1/2}})</tex> si este mai mult un algoritm teoretic decat unul practic, usor implementabil.

 
h2(#prob3). Problema 3 ({_Interogare_}) - Bursele Agora 2005/2006 Runda 1
 
Se considera un sir $A = (a{~1~}, a{~2~}, ..., a{~N~}) (-100.000 <= a{~i~} <= 100.000)$, format din $N$ numere intregi, precum si $M$ perechi de numere $(x, y) (1 <= N, M <= 100.000)$. Pentru fiecare pereche de indici $(x, y) (1 <= x <= y <= N)$ trebuie determinata subsecventa de suma maxima a subsirului $a{~x~}, a{~x+1~}, ..., a{~y~}$ , subsecventele alese trebuie ss contins cel putin un element.
 
h4. Exemplu
 
Pentru sirul $(-1, 2, 3, -2, 4, -3, 8, -3, 1)$ si intervalele $[1, 5]$, $[4, 8]$ si $[6, 6]$ avem solutiile $7, 9, -3$, date de numerele ingrosate $([-1, *2*, *3*, *-2*, *4*], -3, 8, -3, 1, -1, 2, 3, [-2, *4*, *-3*, *8*, -3], 1, -1, 2, 3, -2, 4, [*-3*], 8, -3, 1)$.
 
h3. Rezolvare
 
Folosind algoritmii liniari din prima problema obtinem un algoritm de complexitate $O(MN)$. Sa vedem cum putem reduce complexitatea folosind alte abordari. Mai intai calculam sirul $sum$ al sumelor partiale. Apoi impartim sirul in $k$ subsecvente de lungimi egale $[n/k]$, pentru fiecare secventa pastrand urmatoarele informatii:
 * $max[i]$ - cea mai mare valoare $sum[j]$, unde $n/k * (i-1) < j <= n/k * i$;
 * $min[i]$ - cel mai mic $sum[j-1]$, unde $n/k * (i-1) < j <= n/k * i$;
 * $best[i]$ - valoarea subsecventei de suma maxima a secventei curente.
Acum, daca vrem sa aflam subsecventa de suma maxima a subsecventei $a[x..y]$, avem doua cazuri posibile:
 1. Daca elementele de indice $x$ si $y$ apartin aceleiasi subsecvente din partitie, atunci putem gasi subsecventa de suma maxima folosind algoritmul liniar direct pe sirul $a[x..y]$ (complexitate $O(n/k)$).
 2. Daca ele nu sunt in aceeasi secventa atunci vom imparti sirul $a[x..y]$ in un prefix de subsecventa din cele ce apartin partitionarii, in un sufix de subsecventa si in zero sau mai multe subsecvente complete ce apartin partitionarii. Acum vom rezolva problema pentru sufix si prefix metoda liniara ( {$O(n/k)$} ), iar apoi in $O(1)$ vom determina pentru fiecare bucata în care este spart sirul $a[x..y]$, subsecventa ei de suma maxima.
Mai ramane sa gasim subsecventa de suma maxima cu capatul in bucati diferite. Pentru doua bucati fixate $i <= j$, subsecventa de suma maxima ce are un capat apartinand primei bucati si $j$ apartinand celei de a doua bucati, subsecventa de suma maxima are valoarea $max[j] – min[i]$. Determinarea subsecventei de suma maxima cu capetele in bucati diferite devine astfel de complexitate $O(k)$. Deci pentru a rezolva o intrebare trebuie sa facem $O(n/k + k)$ calcule. Pentru a reduce complexitatea problemei obtinem pe $k = sqrt(n)$. Complexitatea totala a acestei solutii este $O(N + M sqrt(N))$.
 
Sa vedem ce se intampla pe exemplu:
 a:     $-1 2 3 -2 4 -3  8  -3 1$
 sum: $0 -1 1 4  2 6  3  11  8 9$
 
Sirul e impartit in trei subsecvente $[-1, 2, 3], [-2, 4, -3], [8, -3, 1]$.
 max:  $ 4 6 11$
 min:  $-1 2 8$
 best: $ 5 4 8$
Pentru a raspunde la intrebarea $[1, 5]$ vedem ca acest interval e inpartit in $[1..3]$ si $[4..5]$. Solutia optima pentru $[1..3]$ o avem deja in $best[1] = 5$. Solutia optima pentru $[4..5]$ o determinam folosind algoritmul liniar, ea fiind 4. Acum pentru a determina subsecventa de suma maxima cu un capat in intervalul $[1, 3]$ si celalalt in intervalul $[4, 5]$ folosim $max(sum[i]) - min(sum[j-1])$, unde $4 <= i <= 5$ si $1 <= j <= 3$. Valoarea $max(sum[i])$ o gasim ca fiind $6$ parcurgand intervalul $[4, 5]$, iar valoarea $min(sum[j-1])$ o avem deja calculata in $min[1]$. De aici obtinem rezultatul $7$.
 
O solutie similara poate fi realizata cu ajutorul arborilor de intervale. Mai intai cream arborele de intervale. Pentru fiecare interval aflam elementele $min$, $max$ si $best$ astfel $min[x..y] = minim(min[x..(x+y)/2], min[(x+y)/2 + 1 .. y])$, $max[x..y] = maxim(max[x..(x+y)/2], max[(x+y)/2 + 1 .. y])$, $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 raspunde la intrebarile din problema fiecare interval va fi impartit in $O(log N)$ subintervale canonice care apar in arborele de intervale. Apoi printr-o parcurgere asemanatoare celei din rezolvarea anterioara se poate obtine rezultatul pentru fiecare intrebare in $O(log N)$. Solutia va avea complexitatea $O(N + M log N)$.
In urmatorul desen observam structura unui arbore de intervale pentru un sir cu $16$ elemente. Daca se pune intrebarea $[2, 11]$ acest interval va fi spart in intervalele $[2, 2], [3, 4], [5, 8], [9, 10], [11, 11]$.
 
Prezentam procedura de construire a arborelui, implementata in _java_:
 
== code(java) |
public void build_tree(int index, int low, int high) {
    if (low == high) {
        if (low != 0) aint[index] = new Node(low, high, a[low] - a[low - 1], a[low], a[low]);
        else aint[index] = new Node(low, high, 0, 0, 0);
    }
    else {
        aint[index] = new Node(low, high, -infinity, -infinity, infinity);
        int mid = (low + high) / 2;
        build_tree(2 * index, low, mid);
        build_tree(2 * index + 1, mid + 1, high);
        aint[index].maxS = Math.max(aint[2 * index].maxS,Math.max(aint[2 * index + 1].maxS,aint[2 * index + 1].max - aint[2 * index].min));
        aint[index].max = Math.max(aint[2 * index].max,aint[2 * index + 1].max);
        aint[index].min = Math.min(aint[2 * index].min,aint[2 * index + 1].min);
    }
}
==
 
Si procedura care raspunde la intrebari tot in _java_:
 
== code(java) |
long minPrefix;
int x, y;
public long queryTree(int index, int low, int high) {
    if (x <= low && high <= y) {
        long maxRet = aint[index].maxS;
        if (minPrefix != infinity) {
            maxRet = Math.max(maxRet, aint[index].max - minPrefix);
        }
        minPrefix = Math.min(minPrefix, aint[index].min);
        return maxRet;
    }
    else {
        int mid = (low + high) / 2;
        if (x <= mid && mid < y) return  Math.max(queryTree(2 * index, low, mid), queryTree(2 * index + 1, mid + 1, high));
        else if (x > mid) return queryTree(2 * index + 1, mid + 1, high);
            else return queryTree(2 * index, low, mid);
    }
}
==