else return queryTree(2 * index, low, mid);
    }
}

==

==
 
h2(#prob4). Problema 4 - ACM ICPC NWERC 97, olimpiada online 2000, campion 2001
 
Se da un sir $(a{~1~}, a{~2~}, ..., a{~N~})$ format din $N$ numere intregi. Se cere sa se determine subsecventa $a[i..j]$ care are modulul sumei elementelor minim.
 
h4. Exemplu
 
Pentru sirul $(2, 8, -6, -6, 9, 4, -3)$, subsecventa este $(4, -3)$, avand suma in modul $1 = |4 - 3|$.
 
h3. Rezolvare
 
Facem mai intai sirul sumelor partiale. Pentru oricare doua elemente $sum[i]$ si $sum[j]$ ($i != j$) modulul sumei unei subsecvente din sir va fi $|sum[i] - sum[j]|$. Daca $i < j$ atunci secventa va fi $a[i+1..j]$, iar daca $j < i$ atunci secventa va fi $a[j+1 .. i]$. Astfel, pentru a gasi subsecventa de modul minim trebuie de fapt sa gasim perechea de indici $i$ si $j$ astfel ca $|sum[i] - sum[j]|$ sa fie minim. Sortand sirul sumelor partiale si luand o pereche de indici $i < j$, atunci $sum[i] < sum[j]$, iar $|sum[j] - sum[i]| = sum[j] - sum[i]$. Pentru a gasi perechea $(i, j)$ pentru care $i < j$ si $sum[j] - sum[i]$ este minim, trebuie ca $i$ sa fie egal cu $j + 1$. Astfel obtinem un algoritm de complexitate $O(N log N)$.
 
Sa vedem cum merge pe exemplul prezentat:
 a:     $2  8 -6 -6 9  4 -3$
 sum: $0 2 10  4 -2 7 11  8$
 ind: $0 1  2  3  4 5  6  7$
In sirul $ind$ vom pastra indicii reali ai sumelor parţiale.
 
Dupa sortare avem:
 sum:  $ -2  0 2 4 7 8 10 11$
 ind:   $ 4  0 1 4 5 7  2  6$
O secventa de modul $2$ ar fi cea reprezentata de sumele $8$ si $10$ cu indicii $7$ si $2$. Aceasta secventa este $(-6, -6, 9, 4, -3)$.
Observam ca cea mai mica diferenta intre termeni consecutivi e cea dintre $8$ si $7$ care au indicii $7$ si $5$, de unde obtinem ca subsecventa de modul minim este $(4, -3)$.