[アルゴリズム]プレフィックス和(prefix sum)アルゴリズム(区間の和)

1.数列内の特定領域内のノードの和

連続して列挙されたN個の数がある場合,特定の区間内のすべての数を加算するアルゴリズムを理解する.
しかし,1次元リストで線形探索を行うのではなく,複数の情報と区間を与える際に時間的複雑度を最小限に抑えることを考慮する必要がある.

N個の整数からなる数列がある場合、M個のQueryが与えられる.

各Queryは[Left,Right]情報を含み、その範囲内に存在するすべてのノードの和を導出する.

時間はO(N+M)に制限されている(線形探索であればO(N^M)であり、他のスキームが必要である).

2.接頭辞とアルゴリズム

各Queryは,線形探索を必要とせずに,プレフィックスとアルゴリズム(prefix sum)を用いて区間和を求める.
あらかじめ各数字の和(接頭辞和)を計算して保存し、M個のQueryを見るたびに保存した値を用いて区間和を求める.

N個の数は、各位置についてプレフィックスを計算し、個別のリスト(P)に格納する.

各セグメントの和は、P[right]-P[left-1]である.

3.アルゴリズム実装

#접두사 합을 통한 구간 합 구하는 알고리즘 도출하기
n = 5
data = [10, 20, 30, 40, 50]

#sum result
sum = 0
#prefix sum, index = 0은 0으로 초기화, 노드1부터 계산하는 것임.
prefixSum = [0]

for i in data:
    sum = sum + i
    prefixSum.append(sum)

#구간합 계산
left = 3
right = 4
print(prefixSum[right]-prefixSum[left-1])

4.参考資料

2021易科特-接頭辞連結アルゴリズム
https://www.youtube.com/watch?v=cswJ1h-How0&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=9