いもす法をPythonで学ぶ

いもす法の学習を行ったので、自分なりにまとめます。

いもす法とは，累積和のアルゴリズムを多次元，多次数に拡張したものです．競技プログラミングでは 2 次元 1 次のものまでしか出題されませんが，2012 年の研究成果としてこれをより高次元の空間により高次数のいもす法を適用することにより信号処理分野・画像処理分野において利便性があることがわかっています
https://imoz.jp/algorithms/imos_method.html

引用ページの問題例にそって考えていきます。

喫茶店を訪れるそれぞれの客$i （ 0 \leq i < C）$について入店時刻$S_i$と出店時刻$E_i$が与えられる$（0 \leq S_i < E_i \leq T）$。同時刻にお店にいた客の数の最大値Mはいくつか。という問題。

シンプルに考えるなら0で初期化した長さ$T$の配列に各お客が滞在していた各時刻のカウントを1足す方法です。

S = [3, 4, 5]
E = [7, 6, 8]
C = 3
T = max(E)
table = [0] * T
for i in range(C):
  for j in range(S[i], E[i]):
    table[j] += 1
    
M = 0
for i in range(T):
  if M < table[i]:
    M = table[i]

これは［入店時刻、退店時刻］が[(3, 7),(4, 6),(5, 8)]のときです。5時から6時が3人いるので最大3人です。この計算量はfor文の入れ子構造になっていることから計算量が$O(CT)$とわかります。

一方いもす法は入店時に＋１、退店時にー１を記録し、全体をシミュレートします。

S = [3, 4, 5]
E = [7, 6, 8]
C = 3
T = max(E)
table = [0] * (T + 1)
# 入退店のカウント
for i in range(C):
  table[S[i]] += 1
  table[E[i]] -= 1

# シミュレート
for i in range(1, T):
  table[i] += table[i - 1]
  
M = 0
for i in range(T + 1):
  if M < table[i]:
    M = table[i]

先ほどと違い、for文の入れ子構造が無くなっていることが分かると思います。計算量はカウント時の$O(C)$とシミュレート時の$O(T)$の合計$O(C + T)$になります。

シミュレートが何をやっているかは、図で書くとわかりやすくなるかもしれません。

試しにお客が一人だったとしてシミュレートが何をしているか見てみます。プログラムの中を見るとひとつ前の要素を現在の要素に足し合わせるコードになっているので累積和をとるものだとわかります。