AtCoderの勉強でかねてより累積和の勉強をすすめていた。一段落したので記録しておく。

参考にした記事はこちらです。

1次元累積和はけっこう簡単で、この記事を読めばだいたい理解できる。コードも1次元の配列を使うだけなのでわりとすんなりかける。書き方によって配列要素のインデックスを +1 するのか -1 するのか気をつける程度でなので、1つの問題を解くのにもあまり時間がかからない。例題をいくつか解けば手に馴染んでくる。

しかし、2次元累積和になるとちょっと話が変わってくる。

ゼータ変換のほうがわかりやすい？

2次元累積和を素直に考えると、以下の図のように考えて、このような式で求めていく

s[x+1][y+1] = s[x][y+1] + s[x+1][y] − s[x][y] + a[x][y]

引用元: https://qiita.com/drken/items/56a6b68edef8fc605821

でもこの方法は、ちょっと頭を使わないといけなくてx y の動きとs[x+1][y+1] の結果がなんかしっくりこない。視覚的に動きを見えるようにしたら理解できた。可視化は理解の手助けになる。コードはRubyで書いた。

H, W = 4, 5
A = [
  [1, 1, 1, 1, 1],
  [1, 1, 1, 1, 1],
  [1, 1, 1, 1, 1],
  [1, 1, 1, 1, 1]
]

s = Array.new(H+1){ Array.new(W+1) { 0 } }

print "\e[H\e[2J"
(0...H).each do |i|
  (0...W).each do |j|
    s[i+1][j+1] = A[i][j] + s[i+1][j] + s[i][j+1] - s[i][j]
    puts "(%s, %s)" % [i, j]
    pp s
    sleep 1
    print "\e[H\e[2J"
  end
end

pp s

# 累積和の配列 s
# => [
#  [0, 0, 0, 0, 0, 0],
#  [0, 1, 2, 3, 4, 5],
#  [0, 2, 4, 6, 8, 10],
#  [0, 3, 6, 9, 12, 15],
#  [0, 4, 8, 12, 16, 20]
# ]

一方ゼータ変換で累積和を求める方は直観的に理解しやすく、コードも書きやすかった。

ゼータ変換はこちらで詳しく解説されています。

qiita.com

コードはこんな感じ

H, W = 4, 5
A = [
  [1, 1, 1, 1, 1],
  [1, 1, 1, 1, 1],
  [1, 1, 1, 1, 1],
  [1, 1, 1, 1, 1]
]

s = Array.new(H){ Array.new(W) { 0 } }
(0...H).each do |i|
  (0...W).each do |j|
    if i == 0
      s[i][j] = A[i][j]
    else
      s[i][j] = s[i-1][j] + A[i][j]
    end
  end
end

(0...H).each do |i|
  (0...W).each do |j|
    if j == 0
      s[i][j] += 0
    else
      s[i][j] += s[i][j-1]
    end
  end
end

pp s

# 累積和の配列 s
# => [
#  [1, 2, 3, 4, 5],
#  [2, 4, 6, 8, 10],
#  [3, 6, 9, 12, 15],
#  [4, 8, 12, 16, 20]
# ]