Un algorithme pour trouver rapidement la somme de sections spécifiques d'un tableau. Plus précisément, le calcul nécessaire est effectué à l'avance avec $ O (N) $, et la somme des intervalles spécifiques peut être calculée avec le montant du calcul de $ O (1) $. Ceci est efficace lorsque la somme de sections spécifiques doit être calculée plusieurs fois car la somme de sections spécifiques est calculée par $ O (1) $.
Soit $ a = [a_ {0}, \ dots, a_ {N-1}] $ un tableau de longueur $ N $. À ce stade, l'élément $ n $ ème est $ s_ {n} = s_ {n-1} + a_ {n-1} $ (où $ s_ {0} = 0 $) et la longueur est $ N +. Si vous créez le tableau $ s = [s_ {0}, \ dots, s_ {N}] $ de 1 $ à l'avance, la somme de l'intervalle $ a_ {i} $ à $ a_ {j} $ est $ s_ {j +1} --s_ {i} = s [j + 1] --s [i] $ peut être calculé comme $ O (1) $. Le tableau $ s $ créé à l'avance peut être calculé par le montant du calcul de $ O (N) $ comme suit.
for i in range(N):
s[i+1] = s[i] + a[i]
Vous pourriez penser: "N'est-il pas correct de définir $ s_ {n} = s_ {n-1} + a_ {n} $?", Mais alors la somme des intervalles $ a_ {i} $ à $ a_ {j} $ Est
\begin{cases}
s_{j} & (i = 0) \\
s_{j} - s_{i-1} & (i \geq 1)
\end{cases}
Puisqu'il est nécessaire de distinguer les cas, $ s_ {n} = s_ {n-1} + a_ {n-1} $ (cependant, $ s_ {0} = 0 $).
Rendez possible d'écrire la somme cumulée sans penser à rien! --Qiita https://qiita.com/drken/items/56a6b68edef8fc605821