累積和とかの話

虹の龍@ねんねもどへた @nijinoryu

Nailsなにあれ理論和とか理論積って何

Masaki Hara @qnighy

@nijinoryu 論理和と論理積？

虹の龍@ねんねもどへた @nijinoryu

@qnighy 論理でしたか。ありがとうございます。　解説スライド拝見したのですが、さっぱりでしたorz

Masaki Hara @qnighy

@nijinoryu Nails(joi-2012-ho)の解説スライドには理論和・論理和・理論積・論理積のいずれの単語も出てこないけど，累積和のこと？

虹の龍@ねんねもどへた @nijinoryu

@qnighy 今確認してきました。ごめんなさい、その累積和です。　このスライドで初めて知った単語です。どういうものなんでしょうか

Masaki Hara @qnighy

@nijinoryu 一般に，数列a, b, c, d, ... に対して，a, a+b, a+b+c, a+b+c+d, ... という数列をその累積和といいます．整数列a, b, c, d, ... が与えられたとき，その累積和を計算する方法はわかりますか？

虹の龍@ねんねもどへた @nijinoryu

@qnighy 数列a, b, c, d,...に対する累積和はわかりません。　数列{a[i]}に対する累積和を求めるのは総和Σで計算できる、と思います。

Masaki Hara @qnighy

@nijinoryu a, b, c, d, ... という表現はわかりづらかったかもしれませんが，{a[i]}と同じことです．

Masaki Hara @qnighy

@nijinoryu さっきのを言い換えると，数列a[0], a[1], a[2], a[3], ... に対して，a[0], a[0]+a[1], a[0]+a[1]+a[2], a[0]+a[1]+a[2]+a[3], ... という数列をその累積和といいます．

Masaki Hara @qnighy

@nijinoryu 総和Σで計算できる，というのはそのとおりで，{a[i]}の累積和を{b[n]}とするとb[n] = (Σ(i=0 → i=n) a[n]) と書くことができます．

Masaki Hara @qnighy

@nijinoryu この(総和によって定義した)式の通りに計算するとして，累積和の最初のn項を求めるのは，どれくらいの時間で行えるかわかりますか？

虹の龍@ねんねもどへた @nijinoryu

@qnighy n回の足し算で計算できると思います。O(n)時間、でよいでしょうか

Masaki Hara @qnighy

@nijinoryu 全体でO(n)時間という意味ですか？

虹の龍@ねんねもどへた @nijinoryu

@qnighy 第n項を求めるのがO(n)です。第1項から第n項までを求めるにはO(Σ(i=1 → i=n) i)で、およそO(n^2)でしょうか

Masaki Hara @qnighy

@nijinoryu はい．式の通りに計算するとそのようになります．では，それをより高速に計算することはできますか？

虹の龍@ねんねもどへた @nijinoryu

@qnighy 数列a[n]の累積和をb[n]とすると、b[i+1] = b[i] + a[i+1] と計算できるので、O(n)にできると思います

Masaki Hara @qnighy

@nijinoryu OKです．累積和自体については十分そうですね．1次元の累積和を予め計算しておくと，例えばa[x]からa[y]までの和を高速に計算することができます．

虹の龍@ねんねもどへた @nijinoryu

@qnighy b[y]-b[x]でO(1)で求められちゃうんですね！　すごいですっ！

Masaki Hara @qnighy

@nijinoryu はい．これは2次元で矩形の範囲の総和を求めるのにも使えますがわかりますか？

虹の龍@ねんねもどへた @nijinoryu

@qnighy 矩形の範囲の総和、というのは２次元配列table[n][m]での、全ての要素の総和、ということですか

Masaki Hara @qnighy

@nijinoryu ２次元配列を表にして並べたときに，「指定された長方形領域内にあるもの全ての和を求めてください」という問題がたくさん与えられることを考えてみてください．長方形領域は右上と左下の座標によって指定されます．

虹の龍@ねんねもどへた @nijinoryu

@qnighy 2次元配列table[n][m]を考えます。この2次元配列の理論和sum[n][m]は　sum[i+1][j+1] = sum[i][j+1] + sum[i+1][j] + table[i+1][j+1] で求められます。計算量はO(nm)です

虹の龍@ねんねもどへた @nijinoryu

@qnighy 右上の座標(x[1], y[1]), 左下の座標(x[2], y[2])が 与えられた時、 ans = sum[x[1]][y[2] - sum[x[2]-1][y[2]] - sum[x[1]][y[1]-1] + sum[x[2]-1][y[1]-1]

虹の龍@ねんねもどへた @nijinoryu

@qnighy で求めることができます（O(1)） 入力がq組あれば、全体の計算量はO(nmq)になる、と思います

Masaki Hara @qnighy

@nijinoryu いいですね，そんな感じでOKです(向きとか境界条件はちゃんと確認してないけどまあそこはたぶん大丈夫でしょう)