※有料会員になるとこの動画をご利用いただけます
詳しい説明を読む
＃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]の和に対応します。