競技プログラミングの鉄則
A06
B06
クリア！
■累積和
あるイベントの5日間の来場者数が[10,15,22,33,20]人のとき、何日目から何日目までの来場者を計算する場合を考える。
例えば1日目から3日目の来場者数は、10＋15＋22＝47人、2日目から4日目の来場者数は、15＋22＋33の70人、と直接計算しても良いが、
S[i]としてi日目までの来場数の合計をあらかじめ計算しておくと(0日目までも含めて、S=[0,10,25,47,80,100]）、
例えば2日目から4日目の来場者数は、S[4]-S[2-1]＝80-10=70と計算することができる。
1日目から3日目は、S[3]-S[0]＝47-0=47
3日目から5日目は、S[5]-S[2]＝100-25＝75（直接計算22＋33＋20＝75）