累積和とかの話

Masaki Hara @qnighy

@nijinoryu えーと，sumの値は事前計算しておくことができるので計算量は落ちませんか？

虹の龍@えちえちイラストRTbot @nijinoryu

@qnighy そうでした！　O(nm)の処理をした後にO(1)の処理をq回するので、全体ではO(nm+q)でしょうか

Masaki Hara @qnighy

@nijinoryu 正解です．累積和を求めておくときの事前計算があるので，一回だけ必要なときは無駄ですが，同じデータに対してたくさんクエリが来るときはこのように高速になります．

虹の龍@えちえちイラストRTbot @nijinoryu

@qnighy ありがとうございます。O(nmq)とO(nm+q)では随分な違いですものね

Masaki Hara @qnighy

@nijinoryu さて，本題に戻ります．まず，一次元の場合を考えます．数列0, 0, 0, 1, 0, 0, 0, 0, -1, 0, 0, 0の累積和はどうなりますか？

虹の龍@えちえちイラストRTbot @nijinoryu

@qnighy 0,0,0,1,1,1,1,1,0,0,0,0です

Masaki Hara @qnighy

@nijinoryu OKです．では，さっきの数列のうち2つの項を変更して，0, 0, 0, 1, 0, 1, 0, 0, -1, 0, 0, -1とします．累積和はどのように変わりますか？

虹の龍@えちえちイラストRTbot @nijinoryu

@qnighy 0,0,0,1,1,2,2,2,1,1,1,0です。　1の後に-1が来る前にもう一度1が来たので、累積和に2が登場しました

Masaki Hara @qnighy

@nijinoryu もとの数列は「5番目が1増加，11番目が1減少」しました．一方，その累積和は「5番目から10番目までが1ずつ増加した」となりました．OKですか？

虹の龍@えちえちイラストRTbot @nijinoryu

@qnighy はい。a<bで、a番目が1増加、b番目が1減少すると、その累積和はa番目からb-1番目が1ずつ増加します

Masaki Hara @qnighy

@nijinoryu では，「a[q]からb[q]-1番目(a[q]<b[q])にそれぞれ1を足してください」というクエリがたくさん来るとします．最終結果だけわかればよいとします．どのようにすると効率的ですか？

虹の龍@えちえちイラストRTbot @nijinoryu

@qnighy クエリiに対してa[i]番目からb[i]-1番目までに1を足していると、もとの数列の長さをnとして最悪O(nq)かかります。　しかし、数列c[n]を導入して、c[a[i]]に1,c[b[i]]に-1を加える処理をq回行い、c[n]の累積和d[n]をもとの数列に足す

虹の龍@えちえちイラストRTbot @nijinoryu

@qnighy するとO(q+n)で処理できます

Masaki Hara @qnighy

@nijinoryu OKです．数列の初期値が0のときはもう少し簡単になりますね．このように，あらかじめ差分だけを記録しておいて最後に累積和を取る方法を，競プロ界隈ローカルな業界用語で「いもす法」と呼ぶ習慣があるので覚えておくと便利かもしれません．

Masaki Hara @qnighy

@nijinoryu そして，これを2次元に対して適用したものが，Nailsの解説の5ページあたりから解説されているものです．