Nous avons un problème sur la façon de calculer rapidement les sommes sur l'intervalle l...r dans un tableau statique a en moins de O(n) asymptotique.
Divisons le tableau a en k blocs de même taille et calculons d'abord la somme des éléments pour chacun d'eux.
Maintenant, en répondant à la requête, nous pouvons parcourir les éléments du tableau a et les ajouter au résultat, même si l'un des blocs se trouve à l'intérieur du segment, alors nous pouvons ajouter sa somme au résultat et ignorer le éléments de ce bloc.
Le nombre maximum d'opérations par requête avec cet algorithme est n / k + k, donc le k optimal est égal à la racine carrée de n.