Ein Algorithmus zum schnellen Auffinden der Summe bestimmter Abschnitte eines Arrays. Insbesondere wird die erforderliche Berechnung im Voraus mit $ O (N) $ durchgeführt, und die Summe spezifischer Intervalle kann mit dem Berechnungsbetrag von $ O (1) $ berechnet werden. Dies ist effektiv, wenn die Summe bestimmter Abschnitte mehrmals ermittelt werden muss, da die Summe bestimmter Abschnitte mit $ O (1) $ berechnet wird.
Sei $ a = [a_ {0}, \ dots, a_ {N-1}] $ ein Array der Länge $ N $. Zu diesem Zeitpunkt ist das $ n $ -te Element $ s_ {n} = s_ {n-1} + a_ {n-1} $ (wobei $ s_ {0} = 0 $) und die Länge $ N + ist. Wenn das Array $ s = [s_ {0}, \ dots, s_ {N}] $ von 1 $ im Voraus erstellt wird, beträgt die Summe des Intervalls $ a_ {i} $ bis $ a_ {j} $ $ s_ {j +1} --s_ {i} = s [j + 1] --s [i] $ kann durch den Berechnungsbetrag von $ O (1) $ berechnet werden. Das im Voraus erstellte Array $ s $ kann wie folgt durch den Berechnungsbetrag von $ O (N) $ berechnet werden.
for i in range(N):
s[i+1] = s[i] + a[i]
Sie könnten denken: "Ist es nicht in Ordnung, $ s_ {n} = s_ {n-1} + a_ {n} $ zu setzen?", Aber dann die Summe der Intervalle $ a_ {i} $ auf $ a_ {j} $ Ist
\begin{cases}
s_{j} & (i = 0) \\
s_{j} - s_{i-1} & (i \geq 1)
\end{cases}
Da zwischen Fällen unterschieden werden muss, ist $ s_ {n} = s_ {n-1} + a_ {n-1} $ (jedoch $ s_ {0} = 0 $).
Machen Sie es möglich, die kumulative Summe zu schreiben, ohne an irgendetwas zu denken! --Qiita https://qiita.com/drken/items/56a6b68edef8fc605821