An algorithm for quickly finding the sum of specific intervals in an array. Specifically, the necessary calculation is performed in advance with $ O (N) $, and the sum of specific intervals can be calculated with the amount of calculation of $ O (1) $. This is effective when it is necessary to obtain the sum of specific sections many times because the sum of specific sections is calculated by $ O (1) $.
Let $ a = [a_ {0}, \ dots, a_ {N-1}] $ be an array of length $ N $. At this time, the $ n $ th element is $ s_ {n} = s_ {n-1} + a_ {n-1} $ (where $ s_ {0} = 0 $) and the length is $ N +. If the array $ s = [s_ {0}, \ dots, s_ {N}] $ of 1 $ is created in advance, the sum of the interval $ a_ {i} $ to $ a_ {j} $ is $ s_ {j. +1} --s_ {i} = s [j + 1] --s [i] $ can be calculated as $ O (1) $. The array $ s $ created in advance can be calculated by the amount of calculation of $ O (N) $ as follows.
for i in range(N):
s[i+1] = s[i] + a[i]
You might think, "Isn't it okay to set $ s_ {n} = s_ {n-1} + a_ {n} $?", But then the sum of the intervals $ a_ {i} $ to $ a_ {j} $ Is
\begin{cases}
s_{j} & (i = 0) \\
s_{j} - s_{i-1} & (i \geq 1)
\end{cases}
Since it is necessary to distinguish between cases, $ s_ {n} = s_ {n-1} + a_ {n-1} $ (however, $ s_ {0} = 0 $).
Make it possible to write the cumulative sum without thinking about anything! --Qiita https://qiita.com/drken/items/56a6b68edef8fc605821