任意のサブ配列内のすべてのアイテムの合計を見つけるのに最適なアルゴリズムは何ですか？

Question

問題があり、OK-ishソリューションです。私はそこに良い解決策があることを望んでいます。

問題

私は約20万の整数の配列を持っています。 2つの指標、i1とi2が与えられた場合、i1とi2の間のすべての要素の合計を計算する必要があります。配列の各整数は1〜4です。例：

a = [1, 3, 2, 4, 3, 2, 4, 1]; 
subsection_sum(a, 0, 3); // returns 6: (1 + 3 + 2) 

この操作は約20万回実行されるため、かなり高速にする必要があります。 forループの単純なカウンタはO（n）であり、非常に遅い。構築後は配列が決して変更されないので、比較的高価な前処理段階を持つことは問題ありません。

私の最善の解決策これまで

このアルゴリズムは、Oで動作（ログn）時間：

第1のパッドゼロで元の配列の長さが2の累乗になるまで。次に、配列を2つの等しい部分に分割し、それぞれの合計を格納します。その後、配列を四半期に分割し、それぞれの合計を格納します。その後8分。配列がセクション2要素の長さに分割されるまでこれを続けます。上記8素子アレイのために、この2つのステップ取る：

halves = [(a[0] + a[1] + a[2] + a[3]), (a[4] + a[5] + a[6] + a[7])] 
quarters = [(a[0] + a[1]), (a[2] + a[3]), (a[4] + a[5]), (a[6] + a[7])] 

を次に2つの指標が与えられると、時間（ログn）Oでsubsection_sumを動作することが可能です。たとえば、subsection_sum（a、2,7）==四半期[1] +半分[1]です。

Answer 1

累積合計を含む補助配列を導入します。すなわち、補助配列の要素iは、元の配列の要素0〜iの合計を有する。サブアレイの合計は、補助配列からの2つの要素の差にすぎません。これにより一定の時間で結果が得られますO(1)。

これが問題に与えられたsubsection_sum機能で不変に依存,:

subsection_sum(a, 0, i2) = subsection_sum(a, 0, i1) + subsection_sum(a, i1, i2) 

私はi1 <= i2を想定しています。再配置、我々は持っている：

subsection_sum(a, i1, i2) = subsection_sum(a, 0, i2) - subsection_sum(a, 0, i1) 

注右側の和が両方0から始めること。補助配列は、すべてiの場合、0からの合計値をキャッシュすると見ることができます。subsection_sum(a, 0, i)

Answer 2

もしO(n)追加のストレージを得ることができる場合は、そのi番目の要素入力アレイ内i（両端を含む）を介してインデックス0における要素の和であるルックアップテーブルを作成することができます。擬似コードで：

def computeLookupTable(arr): 
    let n = arr.length 
    let lookupTable = new Array() 

    lookupTable[0] = arr[0] 

    for i=1 to n: 
     lookupTable[i] = arr[i] + lookupTable[i-1] 

    return lookupTable 

は、その後、一定の時間を要する違い

lookupTable[i2] - lookupTable[i1] 

を取ることによってi1とi2間array内のすべての要素の合計を計算するために、この表を使用することができます。