累積和は競技プログラミングでは当たり前のようによく出てくるが、配列の逆順からの累積和(逆累積和ということにする)もたまーに出る。少しややこしいのでメモ。 逆累積和は練習問題に上げた問題の他に全方位木DPでも登場したりするので、まぁまぁ重要である。
累積和のポイント
https://qiita.com/drken/items/56a6b68edef8fc605821 が詳しいが、
- 配列は0-indexed
- 累積和の配列(
cum)は1-indexed。cum[0]は0、cum[size] = sum
としてやると区間[left, right)の和を求める際にcum[right] - cum[left]の形で求めることができ、1や-1などの余分な定数が不要で便利になる。
逆累積和のポイント
ABC 125 C - GCD on Blackboardはその典型だが、累積和と逆累積和を両方導出しておく必要があり、逆順に並び替えるなどで逆累積和を累積和として帰着することができない。
結論から言うと、以下のポイントに気をつければ、逆累積和が楽に実装できる。特に一番目の項目！
- 配列は1-indexed(配列の大きさは
size+1) - cum[k]: 2-indexedとする。配列のサイズは
size+2とする。なので、cum[1] = 0, cum[num+1] = sum (cum[0]は使用しない) - rcum[k]: num-1から累積するようにする。配列のサイズは同じく、
size+2。例えば、rcum[num] = 0, rcum[num-1] = arr[num], .. rcum[0] = sum, (rcum[num+1]は使わない)
表にすると以下のようになる：
| idx | 0 | 1 | 2 | 3 | ... |
|---|---|---|---|---|---|
| arr | x | arr[1] | arr[2] | arr[3] | ... |
累積和cum |
- | 0 | arr[1] | arr[1]+arr[2] | ... |
逆累積和rcum |
sum | arr[num]+...+arr[2] | arr[num]+...+arr[3] | arr[num]+...+arr[4] | ... |
| idx | ... | num-2 | num-1 | num | num+1 |
|---|---|---|---|---|---|
| arr | ... | arr[num-2] | arr[num-1] | arr[num] | x |
累積和cum |
... | arr[1]+...+arr[num-3] | arr[1]+...+arr[num-2] | arr[1]+...+arr[num-1] | sum |
逆累積和rcum |
... | arr[num]+arr[num-1] | arr[num] | 0 | x |
ここで、sumは配列の総和。
実装はおおよそ以下のようにすれば良い：
int size = get_int(); static int arr[NUM_MAX+2]; fget_array(&arr[1], size); static int cum[NUM_MAX+2]; int i; for(i = 1; i <= size; i++) { cum[i+1] = add(cum[i], arr[i]); } static int rcum[NUM_MAX+2]; for(i = size; i >= 1; i--) { rcum[i-1] = add(rcum[i], arr[i]); }
実装すればわかるが、arrayを1-indexedとすることを念頭におけば、あとは累積和、逆累積和のindexをどの様に処理すればよいかは自然と決定できる。
こうしておくと、[1, end)の区間は、cum[end]で良いし、(start, size]の区間はrcum[start]でよい。
ABC 125 C - GCD on Blackboard の問題は、要素一つ抜いた場合の答えをindex=1~nについてそれぞれ求めれば良いから、単純に以下のように書ける：
for(i = 1; i <= num; i++) { int res = gcd(cum[i], rcum[i]) // 要素arr[i]を抜いたときの答え }
gcdの右辺と左辺のiが共通しているが、[1, i)と(i, num]の区間の答えなので、resはiのみ除く和を求めていることになる。
練習問題
| 例題 | 解答例 |
|---|---|
| ABC 125 C - GCD on Blackboard | 累積和、逆累積和 |
| ABC 095 D - Static Sushi | 環状、累積和、逆累積和 |
他にも募集中です。(たぶんあるはず)
