区間と計算

区間と問題とは、連続してリストされたn個の数の場合、ある特定の区間のすべての数の総和を求める問題である.例えば、5つのデータからなる数列{10,20,30,40,50}があると仮定する.2番目の数から4番目の数の合計は20+30+40で90になります.
これらの区間および計算の問題は、通常、複数のクエリからなる問題の形式で発生します.複数の区間に対してそれぞれ和を求めることが要求される.たとえば、M個のクエリーが存在するとします.各クエリーは「左」と「右」で構成され、「左」と「右」の部分を表します.したがって、M個のクエリがある場合、典型的な「計算区間和」の問題は、すべてのクエリの区間和を出力することである.
M個のクエリに対してそれぞれの区間和を計算すると,このアルゴリズムはO(NM)の時間的複雑さを有する.なぜなら、M個のクエリを実行するたびに、リスト全体のすべての区間数(1番目からN番目)を計算する必要があるからです.従って,O(NM)は時間的に複雑度が高く,データ量が大きいと複雑度が問題を解決できない.
アルゴリズムを設計する際に常に考慮しなければならないのは、予め保存されている情報が多ければ多いほど、それが役に立つことです.クエリーはMですが、N個のクエリーは1回指定した後も変更されません.したがって、N個のクエリーに対して任意の「処理」を実行し、その後、M個のクエリーがあるたびに区間和をすばやく求めることができます.
「プレフィックス和」(Prefix Sum)は、区間の計算および最も一般的な方法です.各クエリの区間和を迅速に計算するために,N個の位置のプレフィックス和をあらかじめ解くことができる.ここで、接頭辞とは、リストの先頭から特定の位置までの合計を表します.

高速計算区間和のアルゴリズム

N個の数字のプレフィックスを計算し、アレイPに格納する.

M毎の問合せ情報[L,R]を調べると、区間和はP[R]−P[L−1]となる.

たとえば、5つのデータがあるとします.

この5つのデータの接頭辞和を計算します.

上記のアルゴリズムに従って各クエリに入ると,P[R]−P[L−1]を計算すると区間和が得られる.したがって,各クエリの計算時間はO(1)である.従って、N個のデータとM個のクエリがある場合、区間全体の和を計算する動作は、O(N+M)の時間的複雑さを有する.

取得プロセス

3つのクエリーがあると仮定すると、区間和を求めるプロセスは次のとおりです.
1.最初のクエリは[1,3]と呼ばれ、最初の数から3番目の数までの区間和を尋ねる.この場合、P[3]-P[0]=60が答えになります.
2.2番目のクエリは[2,5]と呼ばれ、2番目の数から5番目の数までの区間和を尋ねる.この場合、P[5]-P[1]=140が答えとなる.
3.3番目のクエリは[3,4]と呼ばれ、3番目の数から4番目の数までの区間和を尋ねます.この場合、P[4]-P[2]=70が答えとなる.

ソースコード

# 데이터의 개수 N과 전체 데이터 선언
n = 5
data = [10, 20, 30, 40, 50]

# 접두사 합(Prefix Sum) 배열 계산
sum_value = 0
prefix_sum = [0]
for i in data:
    sum_value += i
    prefix_sum.append(sum_value)

# 구간 합 계산(세 번째부터 네 번째 수까지)
left = 3
right = 4
print(prefix_sum[right] - prefix_sum[left - 1])