Écrire sommes prefixes(t) , qui rend le tableau des sommes des i…

def sommes_prefixes(t):
    """Tableau p tel que p[i] soit la somme des i premiers éléments.

    Postcondition : len(p) == len(t) + 1, p[0] == 0, et
                    p[i+1] - p[i] == t[i] pour tout i.
    """
    p = [0]
    for x in t:
        p.append(p[-1] + x)
    return p

sommes_prefixes([3, 1, 4, 1, 5])      # [0, 3, 4, 8, 9, 14]

L'invariant. Après avoir traité les $i$ premiers éléments, p a $i+1$ cases et p[k] vaut la somme de t[0..k-1] pour tout $k\le i$. L'initialisation pose p = [0] : la somme de zéro élément vaut $0$, ce qui est l'élément neutre de l'addition — et c'est pourquoi le tableau a une case de plus que t.

L'usage. La somme d'une tranche quelconque se lit alors par une soustraction :

$$\text{t[i]}+\text{t[i+1]}+\cdots +\text{t[j-1]}=\text{p[j]}-\text{p[i]}.$$

Un précalcul linéaire, et toute somme de tranche coûte ensuite une opération au lieu de $j-i$. C'est le même marché que le dictionnaire du chapitre 5 : payer un parcours une fois pour répondre instantanément mille fois.

La vérification. Sur $2000$ tableaux tirés au hasard, on a testé toutes les tranches de chacun :

assert all(p[j] - p[i] == sum(t[i:j])
           for i in range(len(t) + 1) for j in range(i, len(t) + 1))

$2000$ cas passent, tranches vides comprises — pour lesquelles la formule donne $0$, ce qui est juste.