Qu'il y ait un tableau. En l'absence de changements, on peut trouver rapidement (plus vite qu'une ligne) la valeur de certaines fonctions sur un sous-segment de ce tableau. Pour ce faire, nous devons utiliser de la mémoire supplémentaire et effectuer un pré-calcul.
Par exemple, nous devons trouver rapidement la somme sur un segment du tableau.
Obtenons un tableau de sommes de préfixes, dans lequel l'indice i sera la somme de tous les éléments du tableau avec des indices inférieurs ou égaux à i.
un[] – tableau donné, p[] – tableau de sommes de préfixes
Nombre de tableaux p :
Évidemment p[0] = a[0]. Notez que nous pouvons facilement recalculer p[i] via p[i – 1], car le montant sur le préfixe i est le montant sur le préfixe i – 1 + a[i].
Ainsi, le code de calcul des sommes de préfixe ressemble à ceci :
entier a[n], p[n] ;
p[0] = un[0< /span>] ;
pour (int i = 1 ; je < n; je++)
p[i] = p[i - 1] + un[i] ;
De plus, nous notons que la somme sur le segment – la différence entre les deux sommes sur le préfixe.
Vert = rouge – bleu
Ainsi, s'il faut trouver la somme sur l'intervalle [l,r], alors la réponse est p[r] – p[l-1].
Cependant, si je – 1 élément peut ne pas exister. Afin de se passer de if’s, vous pouvez saisir une indexation à 1, et a[0] et p[0] auront des valeurs neutres (0 pour la somme).
Notez que cette technique est un cas particulier de la formule d'inclusion-exclusion, de cette manière, il est possible de stocker non seulement des sommes, mais également d'autres fonctions, telles que la multiplication et le xor.