累積和 Python

累積和

和を累積していく探索法

計算結果を都度、配列に格納して不要な再計算をせずにデータを活用する。

前処理の結果を保存することで結果(クエリ)が速く返ってくる。

calc.py

arr = [1,2,3,4,5,6]
num = len(arr)
result = [0]*num #結果を格納
for i in range(0,num):
    result[i] = result[i-1] + arr[i]
    
print(result)#[1, 3, 6, 10, 15, 21]

#1~4まで計算した値が欲しい場合
print(result[3]) # 10