h2. Cazul unidimensional

Din modul în care a fost enunţată problema, rezultă că operaţiile efectuate asupra unui tablou unidimensional; aşadar, acesta este cazul unidimensional al problemei. Vom prezenta în continuare trei algoritmi care pot fi folosiţi pentru rezolvarea problemei şi apoi le vom studia performanţele.

Din modul în care a fost enunţată problema, rezultă că operaţiile sunt efectuate asupra unui tablou unidimensional; aşadar, acesta este cazul unidimensional al problemei. Vom prezenta în continuare trei algoritmi care pot fi folosiţi pentru rezolvarea problemei şi apoi le vom studia performanţele.

h3. Algoritmul naiv

Trebuie observat faptul că algoritmul este acelaşi dacă operaţia de însumare este înlocuită cu o alta (calcularea produsului, stabilirea minimului etc.).
h3. Vector de sume

 
O altă idee este de a menţine un vector $S$ cu semnificaţia $S ~i~ = suma elementelor din subsecventa <1, i>$. Astfel, răspunsul la o întrebare $(x, y)$ va fi $S ~y~ - S ~x-1~$, ce se poate calcula în timp constant. Însă, când se modifică un element $a ~i~$ trebuie modificate toate sumele $S ~i~, S ~i+1~ ... S ~n~$, deci timpul necesar pentru o modificare este liniar proporţional cu lungimea şirului.
 
Implementarea (scrisă in pseudocod) este aceasta:
 
== code(cpp) |
// iniţializări
 
scrie „Introduceţi numărul de elemente:”
citeşte N        // dimensiunea şirului
pentru i = 1, N execută
    S[i] = 0        // valorile iniţiale sunt nule
sfârşit pentru
scrie „Introduceţi codul operaţiei:”
 
citeşte cod
cât timp cod <> 3 execută
    dacă cod = 1 atunci    // modificare
        scrie „Introduceţi indicele elementului care va fi modificat:”
        citeşte ind
        scrie „Introduceţi valoarea care va fi adunată (valoare negativă pentru scăderi):”
        citeşte val
        pentru i = ind, n execută
            S[i] = S[i] + val
        sfârşit pentru
    altfel    // interogare
        scrie „Introduceţi extremităţile subsecvenţei:”
        citeşte st, dr
        scrie „Suma elementelor subsecvenţei este: ”, S[dr] - S[st - 1]
    sfârşit dacă
    scrie „Introduceţi codul operaţiei:”
    citeşte cod
sfârşit cât timp
==
 
h3. Arbori de intervale