トップ 差分 一覧 ソース 検索 ヘルプ RSS ログイン

imos法・累積和

[アルゴリズム]

練習のための問題は 競技プログラミングの履歴

両者の違いについては 競技プログラミングにおけるimos法・累積和問題まとめ がわかりやすい

二次元累積和 を書いているので、それも参考にどうぞ。

累積和

   累積の和をとっておくと、区間の総和がO(1)で取得できる 参考
   二次元に拡張することもできる

  アルゴリズム

  • 基本的な方針
    • まず必要な分だけ配列を用意する
    • クエリを仕込む
    • 配列全体に array[n] += array[n-1] を実行する
array = Array.new(N){0}

# とても簡単な感じに
array[35] = +1
array[40] = -1

for i in 1...array.length
  array[i] += array[i-1]
end

いもす法

   一定区間にある数を足すクエリを仕込みO(1),後処理O(N)で行う方法 本家解説
   普通は0次1次元であるが、高次高次元に拡張できる(らしい)

  詳しい解説

  練習問題

問題

下のような形式でユーザが欲しがる色が与えられるので、もっとも人気のある色を求める

  • ユーザはa_n ~ b_nまでの色がほしい
  • 要は、区間がたくさん与えられる. もっとも区間に被覆されてる頂点のその被覆数を出力しなさい
n
a_1 b_1
a_2 b_2
...
a_n b_n

解答

入力が以下の場合

4
0 2
2 3
2 4
5 6

1. まず、全体を表す配列を0埋めで用意しとくだで

0 1 2 3 4 5 6 7
0 0 0 0 0 0 0 0

2. 区間の計算 (クエリを仕込む)

  • (0, 2), 0で+1され, 2まではそのまま、3で-1されるので
0 1 2 3 4 5 6 7
1 0 0 -1 0 0 0 0
  • (2, 3), 2で+1され, 3まではそのまま、4で-1されるので
0 1 2 3 4 5 6 7
1 0 1 -1 -1 0 0 0
  • (2, 4), 2で+1され, 4まではそのまま、5で-1されるので
0 1 2 3 4 5 6 7
1 0 2 -1 -1 -1 0 0
  • (5, 6), 5で+1され, 6まではそのまま、7で-1されるので
0 1 2 3 4 5 6 7
1 0 2 -1 -1 0 0 -1

3. 累積和をとる (後処理)

  • 初期値0として、配列のサイズNまで順に足し込んでいく
0 1 2 3 4 5 6 7
1 1 3 2 1 1 1 0

一番被覆されてるのは 2番目で被覆数3

お名前: コメント: