Niz prefiksne sume pohranjuje kumulativne ukupne vrijednosti tako da se bilo koji zbir raspona može odgovoriti u O(1) nakon O(n) pretprocesiranja — umjesto O(n) po upitu.
Ideja
Neka je prefix[i] suma prvih i elemenata. Tada je suma arr[l..r] jednaka .
