累積和
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/03/23 10:14 UTC 版)
累積和（るいせきわ、英: prefix sum, cumulative sum, scan）とは、計算機科学において、数列 
HillisとSteeleは、以下の並列累積和アルゴリズムを提案している。[12]
for i <- 0 to floor(log2(n)) do
for j <- 0 to n - 1 do in parallel
if j < 2i then
xi+1
j <- xi
j
else
xi+1
j <- xi
j 
ワーク効率が高い16入力の並列累積和の回路表現
ワーク効率の良い並列累積和は、以下の手順で計算できる。[5][14][15]
- 隣接する要素の和を計算する（ペアの先頭要素のインデックスが偶数であるものを対象とする）。
- 例：
- 累積和のページへのリンク
