この記事では累積和の使い方について整理します。
累積和について
概要
・配列内の特定の区間の和を素早く求めたい場合に役立つ
・配列の要素数が大きい場合に役立つ
・累積和はリストで保持する
・累積和のリストの各要素は、元の配列の0番目からi番目までの合計値
区間
開区間
開区間(start, end)の場合
元の配列ではstart+1番目からend-1番目の要素を含む。
区間で考えるとstart+1番目からend番目になる。
半開区間
半開区間[start, end)の場合
元の配列ではstart番目からend-1番目の要素を含む。
区間で考えるとstart番目からend番目になる。
閉区間
閉区間[start, end]の場合
元の配列ではstart番目からend番目の要素を含む。
区間で考えるとstart番目からend+1番目になる。
累積和の実装
累積和のリストを作る
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
#入力値(元の配列) input_data = [1,2,3,4,5,6,7,8,9,10] #累積和のリストを用意。元の配列よりも1つ大きくする cumulative_sum = [0]* (len(input_data) + 1) #累積和のリストは後の処理で以下のように作成される #[0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55] #累積和のリストを作成 for i in range(1, len(input_data) + 1): #i番目の累積和はi-1番目の累積和とi-1番目の元の配列のデータの合計値となる cumulative_sum[i] = cumulative_sum[i-1] + input_data[i-1] print(cumulative_sum) #[0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55] |
特定の区間の和を求める
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
#区間[2,4)の和を求める。 #元の配列では2番目～3番目の要素の合計 #区間[start, end)の場合、元の配列ではstart+1 ~ endの要素の合計が求まる print(cumulative_sum[4] - cumulative_sum[2]) #7 #a = 1 2 3 4 5 #s 0 1 '2 3 4' 5 #[0, 1, 3, 6, 10, 15] #元の配列で2番目から4番目の要素の和を求める #累積和のリストでは[2,5)で計算 print(cumulative_sum[5] - cumulative_sum[2]) #12も |
・元の配列のインデックスで考える場合
元の配列でi番目~j番目の要素の合計を求めたい場合、
累積和のリストで、j+1の要素からi番目の要素を引けば良い
・元の配列の区間で考える場合
元配列の区間[start, end)を求めたい場合、
累積和のリストで、end番目の要素からstart番目の要素を引けば良い
まとめ
今回は累積和について確認しました。
コメント