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

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

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