De ce contează?
Imaginează-ți că ții un caiet cu cheltuielile pe fiecare zi a lunii. Cineva te întreabă: „Cât ai cheltuit din ziua 2 până în ziua 5?” Poți să iei caietul și să aduni zilele 2, 3, 4 și 5 de fiecare dată. Dar dacă te întreabă de o sută de ori, despre o sută de intervale diferite, vei reciti aceleași zile la nesfârșit. Soluția deșteaptă: ții pe margine un total „de la început până aici”. Atunci orice interval e o singură scădere între două totaluri. Exact asta fac sumele parțiale.
Intuiția
Ai un vector de numere și ți se cere, de multe ori, suma dintr-un interval [l..r]. În loc să aduni intervalul de fiecare dată, calculezi o singură dată totalurile cumulate: P[i] = suma primelor i elemente. Suma unui interval devine atunci diferența a două totaluri — ca atunci când afli cât ai mers între kilometrul 3 și kilometrul 8 uitându-te la bornă: 8 - 3 = 5, nu numeri pașii.