いもす法 - いもす研 (imos laboratory)

いもす法とは，累積和のアルゴリズムを多次元，多次数に拡張したものです．競技プログラミングでは 2 次元 1 次のものまでしか出題されませんが，2012 年の研究成果としてこれをより高次元の空間により高次数のいもす法を適用することにより信号処理分野・画像処理分野において利便性があることがわかっています． いもす法の基本: 1 次元 0 次いもす法 最もシンプルな「いもす法」は 1 次元上に 0 次関数（矩形関数や階段関数などのように上部が平らな関数）を足すものです． 問題例 あなたは喫茶店を経営しています．あなたの喫茶店を訪れたそれぞれのお客さん i\ (0 \leq i \lt C) について入店時刻 S_i と出店時刻 E_i が与えられます（0 \leq S_i \lt E_i \leq T）．同時刻にお店にいた客の数の最大値 M はいくつでしょうか．ただし，同時刻に出店と入店がある場

[mumumu-tan]

重なりを効率良く計算するいもす法... なんだけど、次元が上がるにつれて、差分をとる手法が魔法に見える(´ー｀; )

[samayotta]

驚き桃の木

[uni745e]

imos法

[Windymelt]

累積和

[koyancya]

なるほど、いもす法

[tanakaBox]

増減を記録しておいて、後で一気に計算。

[fcicq]

calculate the derivative function (even higher dimensional / strange shape) is the key here.

[daimatz]

ほー