15.4. Prefix Sumへの適用

還元の基本的な考え方は出力配列(Prefix-Sum)に結果を更新するのではなく、入力配列を更新することにあります。これは2つの段階を踏むことで行うことができます。

前の項目で計算したのは、このup-sweepに該当します。しかしup-sweepでは出力配列(Prefix-Sum)の計算が定式化されていませんでした。

up-sweepで掃き上げた入力配列を、掃き下げてPrefix-Sumに入力配列の残要素を更新するのがdown-sweepです。

Copyright 2018-2019, by Masaki Komatsu