累積和を使っても二分探索を使っても解ける問題

先週話題にした、ABC(AtCoder Beginner Contest)122のC問題は、累積和を用いて解くのが想定解のようですが、二分探索を用いても解けるという話を、少し一般化して考えてみます。

なお、以下では何も言わずに空間計算量だけ書いた場合、時間計算量も同じオーダーであるとします（それだけの量の空間を触るのに最低限必要な時間です）。

Θ(1)時間で計算可能な特性関数 \mathbb{N}→{0,1}が入力長Ο(N)で与えられる場合

元問題は、このクラスです。 元問題では、特性関数の種として長さNの文字列が与えられます。

累積和

  1. 【前処理】各点での特性関数の値のprefix sumになっている配列を構成します。
  2. 配列アクセスにより、端点での値を得ます。
  3. その差が区間内にある特性関数が1になる点の集合のサイズとなります。

この累積和を使った解法では、

  • 前処理にΘ(Nlog N)空間*1
  • クエリ一つあたりにΘ(log N)時間*2

で解けます。

二分探索を用いる解法

  1. 【前処理】特性関数が1になる点の集合を昇順ソート済み配列として構成します。
  2. 端点を二分探索します。下端（始端）はlower_boundのindex、上端（終端）はupper_boundのindexを得ます。
  3. その差が区間内にある特性関数が1になる点の集合のサイズとなります。

この二分探索を使った解法では、

  • 前処理にΘ(Nlog N)空間
  • クエリ一つあたりにΘ(log N)時間

かかります。後者の解法は定数項が大きく、特に優れた点は見受けられませんが、累積和手法を思いつけなかった場合には有用そうです。

各点での重みが0, 1とは限らない自然数の集合Sであり、それをΘ(1)時間で計算可能な \mathbb{N}→Sが入力長Ο(N)で与えられる場合

Sの要素に何が含まれるかが重要となります。各点での重みのとり得る集合Sの要素で最大のものをKとします。

この場合、累積和手法では何も複雑なことはありません。なお、空間計算量はlog K倍悪化します。

二分探索手法では、要素の重複を許す集合として構成すれば、同じ手法が使えます。しかし、前処理の空間計算量が最悪K倍悪化し、クエリ一つあたりにかかる時間もΟ(log K)倍悪化します。

つまり、KがΘ(N)くらいのオーダーであると、前処理の空間計算量がΘ(N2 log N)となり、N=105の時に2秒以内には完了しないアルゴリズムとなります。

特性関数が、特性関数が1になる点（N以下の自然数）のソートされていない列（長さK）として与えられる場合（K<N）

この場合に累積和手法を適用するには、前処理部分に以下の二つの考え方があります。

  1. ソートしてから累積和。
  2. いもす法。

1.の手法の場合、累積和を取る以上、Θ(Nlog N)の空間の確保は避けられません。 Kとしてあり得るのはN未満の自然数なのでソートはバケットソートとするのが計算量のオーダーとして最善になります。

結局両者のやる仕事は同一になります。

一方、二分探索の手法では、前処理として単にΘ(Klog K)（厳密には、さらにΟ(log N)×Θ(log K)倍の時間がかかるはずです）*3時間かかるソートを行うだけで済みます。

つまり、Kの大きさによっては、二分探索手法が生きる局面があり得ます。それは、KがNに比べて十分に小さい場合です。

特性関数が1となる点が自然数とは限らない（doubleで表されたり、有理数となる）場合

この場合には、累積和手法を適用するのは困難となります。一方、二分探索手法はそのまま適用可能です。

これは、Nが非常に大きく、Kがそれに比べて小さいパターンと同一視できます。

各点での重みが0, 1とは限らない自然数の集合Sであり、その点も自然数とは限らない場合

どちらの手法でも困難に思われます。セグメント木を使うと解けそうです。

Sが任意の有理数である場合も同様だと思います。

まとめ

  • 重みが非零となりうる点の数が少なければ、累積和手法は有効。
  • 各点の重みのとり得る値が非負で小さければ、二分探索手法は有効。
  • 元問題はその両方の性質「重みが非零となりうる点の数はΟ(N)」「各店の重みのとり得る値は0か1」を満たしていたためどちらでも解けた。

*1:通常考慮外とされますが、N未満の自然数を表すにはlogNビット必要な点に注意してください。

*2:N未満の自然数同士の引き算にはΘ(log N)時間かかる点に注意してください。

*3:Ο(log N)倍は、N未満の自然数（Nビットで表せる）の比較にかかる時間（入力がランダムなら平均Θ(1)ですが、最悪の場合はΘ(log N)です）、Θ(log K)項は、要素へのポインタの移動時に書き換えないといけないビット数です（要素の移動だとΘ(log N)ビットの書き換えが必要ですが、要素数が少ない場合要素へのポインタの移動にしてしまえばΘ(log K)ビットで済みます）。