Prefix sum とは

コンピュータサイエンスでは、接頭辞和、累積和、包括走査、または数列x0、x1、x2、…の単純スキャンは、数y0、y1、y2、…の第2のシーケンスであり、入力シーケンスの接頭辞(実行合計):
y0 = x0 y1 = x0 + x1 y2 = x0 + x1 + x2 …
たとえば、自然数の接頭辞の合計は三角の数です。
 
接頭辞の合計は、式yi = yi-1 + xiを使用して各出力値を順番に計算することによって、計算の連続モデルで計算するのは簡単です。しかしながら、計算の容易さにもかかわらず、プレフィックス和は、セクション2.3で導入されたように、ソートのカウントなどの特定のアルゴリズムでは有用なプリミティブであり、関数プログラミング言語におけるスキャン高次関数の基礎を形成する。プリフィックスの合計は、解決すべきテスト問題と、他の並列アルゴリズムのサブルーチンとして使用される有用なプリミティブの両方として、並列アルゴリズムにおいても多く研究されている。
抽象的に言えば、接頭辞の合計は二項連想演算子⊕のみを必要とするため、多くのアプリケーションでは、ポイントの文字列処理へのよく分離されたペア分解を計算するのに便利です。
数学的には、プレフィックス和を取る操作は、有限から無限のシーケンスまで一般化することができます。この文脈では、接頭辞の和は一連の部分和として知られている。プレフィックス和または部分和は、有限または無限シーケンスのベクトル空間上の線形演算子を形成する。その逆は有限差分演算子です。