Summataulukko

Summataulukko on taulukon kaltainen tietorakenne, jonka erikoisuutena on, että minkä tahansa taulukon välin summan pystyy laskemaan tehokkaasti ajassa O(1).

Ideana on muodostaa alkuperäisen taulukon perusteella uusi taulukko, jossa kussakin kohdassa on alkuperäisen taulukon lukujen summa kyseiseen kohtaan asti.

Tarkastellaan esimerkiksi seuraavaa taulukkoa:

Tästä taulukosta muodostuu seuraava summataulukko:

Summataulukossa esimerkiksi kohdassa 4 on luku 20, koska alkuperäisessä taulukossa summa kohtaan 4 asti on 5 + 2 + 7 + 1 + 5 = 20.

Summataulukon avulla minkä tahansa alkuperäisen taulukon välin summan voi laskea ajassa O(1) vähentämällä taulukon viimeistä alkiota vastaavasta yhteissummasta taulukon ensimmäistä alkiota edeltävän alkion yhteissumma.

Esimerkissä taulukossa summa kohdasta 3 kohtaan 7 on 1 + 5 + 4 + 1 + 1 = 12. Tämän saa laskettua summataulukosta näin: 26 - 14 = 12.

Seuraava koodi havainnollistaa summataulukon käyttämistä:

int taulu[10] = {5,2,7,1,5,4,1,1,8,4};
int summat[10];

// summataulukon muodostus
summat[0] = taulu[0];
for (int i = 1; i < 10; i++) {
    summat[i] = summat[i-1]+taulu[i];
}

// summan laskeminen
print("Anna alkukohta: ");
int alku = readint();
print("Anna loppukohta: ");
int loppu = readint();

int summa;
if (alku == 0) {
    summa = summat[loppu];
} else {
    summa = summat[loppu]-summat[alku-1];
}
print("Summa: " + summa);

Summataulukon heikkoutena tavalliseen taulukkoon verrattuna on, että taulukon arvon muuttaminen on hankalaa, koska muutos heijastuu koko summataulukon loppuosaan.

Summataulukon idea on yleistettävissä myös useampaan ulottuvuuteen. Kaksiulotteisessa tapauksessa summataulukon avulla on mahdollista laskea minkä tahansa alitaulukon lukujen summa ajassa O(1).

Ideana on tallentaa summataulukkon kuhunkin kohtaan sellaisen alitaulukon summa, joka alkaa alkuperäisen taulukon vasemmasta ylänurkasta ja päättyy kyseiseen kohtaan.

Seuraavassa on esimerkki kaksiulotteisesta taulukosta ja vastaavasta summataulukosta:

Nyt minkä tahansa taulukon alitaulukon summan voi laskea summataulukon neljän arvon perusteella.

Tarkastellaan esimerkiksi seuraavan summan laskemista:

Tämä saadaan summataulukon arvoista ottamalla pohjaksi summa

vähentämällä siitä summat

ja lisäämällä vielä summa

Kaikki nämä summat ovat summataulukossa, joten tuloksena on 98 - 50 - 39 + 17 = 26.

Sama tulos tulee laskemalla summa alkuperäisestä taulukosta: 5 + 4 + 10 + 1 + 4 + 2 = 26.

Yleisemmin summan kohdasta taulu[a][b] kohtaan taulu[c][d] saa seuraavalla kaavalla, jossa s tarkoittaa summataulukkoa:

s[c][d] - s[a-1][d] - s[c][b-1] + s[a-1][b-1]

Jos a tai b on 0, vastaava kohta kaavassa jää pois.

Seuraavassa koodissa on kaksiulotteisen summataulukon toteutus:

int taulu[4][4] = {{4,13,7,15},
                   {1,3,5,4},
                   {5,11,10,1},
                   {12,1,4,2}};
int summat[4][4];

// summataulukon muodostus
for (int i = 0; i < 4; i++) {
    int rivi = 0;
    for (int j = 0; j < 4; j++) {
        rivi += taulu[i][j];
        summat[i][j] = rivi;
        if (i > 0) summat[i][j] += summat[i-1][j];
    }
}

// summan laskeminen
print("Anna alkukohta: ")
int a = readint();
int b = readint();
print("Anna loppu: ")
int c = readint();
int d = readint();

int summa = summat[c][d];
if (a > 0) summa -= summat[a-1][d];
if (b > 0) summa -= summat[c][b-1];
if (a > 0 && b > 0) summa += summat[a-1][b-1];
print("Summa: " + summa);

Myös kolmiulotteiset ja suuremmat summataulukot ovat mahdollisia, mutta niitä tarvitsee harvoin.