O altă idee ar fi ca pentru fiecare pereche $(i{~1~}, i{~2~})$ fixată să determinăm perechea optimă $(j{~1~}, j{~2~})$. Dacă avem liniile $i{~1~}$ şi $i{~2~}$ fixate atunci problema se transformă din una bidimensională în una unidimensională. Astfel pentru fiecare coloană $j$ vom considera $b[j]$ ca sumă a elementelor $a[i][j]$ cu proprietatea că $i{~1~} <= i <= i{~2~}$. În exemplul nostru, dacă $i{~1~} = 2$ şi $i{~2~} = 3$, atunci avem $b{~1~} = 9 + (-4)$, $b{~2~} = 2 + 1$, $b{~3~} = (-6) + (-4)$ şi $b{~4~} = 2 + 1$. Pentru a rezolva problema unidimensională folosim unul din algoritmii liniari prezentaţi mai sus, astfel obţinându-se un algoritm de complexitate totală $O(N^3^)$. Acest truc de a fixa două linii pentru a transforma problema în una unidimensională este util în multe probleme pe matrice sau cu puncte în plan.

Cel mai bun algoritm cunoscut pentru această problemă are complexitatea <tex>O(N^{3\sqrt{\frac{\log \log N}{\log N}}})</tex> şi este mai mult un algoritm teoretic decât unul practic, uşor implementabil.

Cel mai bun algoritm cunoscut pentru această problemă are complexitatea <tex>O(N^{3\sqrt{\frac{\log \log N}{\log N}}})</tex> [3] şi este mai mult un algoritm teoretic decât unul practic, uşor implementabil.

h2(#prob3). Problema 3 ('SequenceQuery':problema/sequencequery - Bursele Agora 2005/2006 Runda 1)

}
==

Autorul vă recomandă articolele [1] şi [2] pentru o înţelegere mai profundă a structurii de date numită arbori de intervale. Problema poate fi soluţionată şi în $O(N + M)$, dar algoritmul este mult prea complicat pentru un concurs de programare; cei interesaţi pot să îl găsească în [4].
 

h2(#prob4). Problema 4 ( ACM ICPC NWERC 97, olimpiada online 2000, campion 2001 )
Se dă un şir $(a{~1~}, a{~2~}, ..., a{~N~})$ format din numere întregi. Se cere să se determine subsecvenţa $a[i..j]$ care are modulul sumei elementelor minim.

h3. Rezolvare:
Suma _xor_ a două numere este de fapt adunare binară fără transport, fapt care o face similară operaţiei _modulo_. Problema e asemănătoare cu cea a subsecvenţei de modul maxim. Vom obţine toate sumele _xor_ parţiale şi pentru a vedea pentru $sum[i]$ perechea optimă cu care crează o sumă cât mai mare trebuie să găsim acea sumă $sum[j]$ astfel că fiecare bit al lui $sum[i]$ să fie diferit de fiecare bit al lui $sum[j]$, dacă acest lucru este posibil. Pentru a face această căutare cât mai eficientă, putem menţine sumele $sum[i]$ ca şiruri de caractere $0$ sau $1$ într-un trie [5]. Structura de trie pentru cazul când alfabetul are dimensiunea $2$ este identică cu cea de heap. Această soluţie are complexitatea $O(N log C)$.

 
h2(#probp). Probleme propuse
 
Pentru a vă însuşi mai bine tehnicile învăţate în acest articol, autorul vă sugerează să rezolvaţi următoarele două probleme de pe situl infoarena:
 
* Problema 1: 'Balans ':problema/balans
 
* Problema 2: 'Struţi ':problema/struti
 
h2(#bibliografie). Bibliografie
 
1. *Lica Dana*, _Arbori de intervale (Segment Trees)_, GInfo 15/4
2. *Negruşeri Cosmin*, _Căutări Ortogonale, Structuri de date şi aplicaţii_, GInfo 15/5
3. *Takaoka T.*, _Efficient Algorithms for the Maximum Subarray Problem by Distance Matrix Multiplication_
4. *Kuan Yu Chen*, *Kun Mao Chao*, _On the Range Maximum-Sum Segment Query_
5. *Yaw Ling Liu*, *Tao Jiang*, *Kun Mao Chao*, _Efficient Algorithms for Locating the Length-Constrained Heaviest Segments, with Applications to Biomolecolar Sequence Analysis_
6. *Vladu Adrian*, *Negruşeri Cosmin*, Ginfo Noiembrie 2005
7. *Cormen Th.*, *Leiserson Ch.*, *Rivest R.*, _Introducere în algoritmi_, editura Agora