Biar ada beberapa susunan. Sekiranya tiada perubahan, kita boleh dengan cepat (lebih pantas daripada garis) mencari nilai beberapa fungsi pada subsegmen tatasusunan ini. Untuk melakukan ini, kita perlu menggunakan memori tambahan dan melakukan pra-pengiraan.
Sebagai contoh, kita perlu mencari jumlah dengan cepat pada beberapa segmen tatasusunan.
Mari dapatkan tatasusunan jumlah awalan, di mana indeks i akan menjadi jumlah semua elemen tatasusunan dengan indeks kurang daripada atau sama dengan i.
a[] – tatasusunan yang diberikan, p[] – tatasusunan jumlah awalan
Kiraan tatasusunan p:
Jelas sekali p[0] = a[0]. Ambil perhatian bahawa kita boleh mengira semula p[i] dengan mudah melalui p[i – 1], kerana jumlah pada awalan i ialah jumlah pada awalan i – 1 + a[i].
Oleh itu, kod untuk mengira jumlah awalan kelihatan seperti ini:
int a[n], p[n];
p[0] = a[0< /span>];
untuk (int i = 1; i < n; i++)
p[i] = p[i - 1] + a[i];
Selanjutnya, kami perhatikan bahawa jumlah pada segmen – perbezaan antara dua jumlah pada awalan.
Hijau = merah – biru
Oleh itu, jika perlu mencari jumlah pada selang [l,r], maka jawapannya ialah p[r] – p[l-1].
Walau bagaimanapun, jika l – 1 elemen mungkin tidak wujud. Untuk melakukan tanpa if’s, anda boleh memasukkan pengindeksan 1 dan a[0] dan p[0] akan mempunyai nilai neutral (0 untuk jumlahnya).
Ambil perhatian bahawa teknik ini ialah kes khas formula kemasukan-pengecualian, jadi dengan cara ini adalah mungkin untuk menyimpan bukan sahaja jumlah, tetapi juga fungsi lain, seperti pendaraban dan xor.