いくつかの配列を考えてみましょう。変更がない場合、この配列のサブセグメント上のいくつかの関数の値を迅速に (1 行よりも速く) 見つけることができます。これを行うには、追加のメモリを使用し、事前計算を行う必要があります。
たとえば、配列の一部のセグメントの合計をすばやく見つける必要があります。
プレフィックス合計の配列を取得しましょう。インデックス i は、インデックスが i 以下である配列のすべての要素の合計になります。
a[] –指定された配列、p[] –プレフィックスの合計の配列
配列数 p:
明らかに p[0] = a[0] です。 p[i – を介して p[i] を簡単に再計算できることに注意してください。 1]、なぜならi プレフィックスの金額は、i プレフィックスの金額です。 1 + a[i]。
したがって、プレフィックスの合計を計算するコードは次のようになります。
int a[n], p[n];
p[0] = a[0< /スパン>];
の (int i = 1; i < n; i++)
p[i] = p[i - 1] + a[i];
さらに、セグメントの合計は – であることに注意してください。プレフィックスの 2 つの合計の差。
緑 = 赤 –青
したがって、区間 [l,r] の合計を求める必要がある場合、答えは p[r] – になります。 p[l-1]。
ただし、– 1 つの要素が存在しない可能性があります。 if を使用しないようにするには、1-インデックスを入力すると、a[0] と p[0] が中立値 (合計は 0) になります。
この手法は包含排他式の特殊なケースであるため、この方法では合計だけでなく、乗算や XOR などの他の関数も保存できることに注意してください。