※有料会員になるとこの動画をご利用いただけます
詳しい説明を読む
＃01:累積和とは
このレッスンでは、さまざまな処理を高速化する手法である累積和について学習します。
累積和には、このチャプターで学習した、先頭 0 個の和を考慮するもの (exclusive scan) と、考慮しないもの (inclusive scan) があります。
区間の和を求めるときは、前者を使用すれば場合分けせずにコードを書くことができます。
この方法では、s[i] は先頭 i 個の和を表します。
後者には、先頭に無駄な 0 がないことと、もとの配列だけを使用して求めることができるという利点があります。
この方法では、s[i] は a[i] までの和を表します。
後に説明する「いもす法」でも、こちらを使用するとより簡単に書くことができます。
l から r までの区間で r を含まないものを [l, r) と書き、これを半開区間と呼びます。配列の要素間に差し込む仕切りの位置が、添字 l, r の要素のすぐ左になっていると考えるとわかりやすいです。
また、r を含むものを [l, r] と書き、これを閉区間と呼びます。
先頭 0 個の和を考慮する累積和では、s[i] は a[0, i) の和に対応します。また、s[r] - s[l] は a[l, r) の和に対応します。
先頭 0 個の和を考慮しない累積和では、s[i] は a[0, i] の和に対応します。