UPD: 区間add / 0存在判定 Ω*(N^(1.5)) - よすぽの日記
太古に考え、メモってなかったのですが、最近思い出そうとして苦労したのでメモっておきます。
問題
以下の問題の計算量下界について考えます。
- 長さ $N$ の数列 $a_1, \cdots, a_N$ が与えられる。$N$ 個の以下のクエリを処理する。
- 加算クエリ: $l, r, d$ が与えられるので、 $a_l, ..., a_r$ に $d$ を加算する。
- 調査クエリ: $a_1, ..., a_N$ に $0$ は存在するか？
3-SUM / 使用する予想
今回は、サイズ $M = N^{2/3}$ の 3SUM を、この問題に帰着していきます。3-SUMは $O(M^{2 - \epsilon}) = O(N^{1.333 - \epsilon})$ 時間で解けないと信じられています(参考: wikiや https://lealgorithm.blogspot.com/2018/07/hardness-in-p-seth.html 等) 。
今回は 3-SUM の variant として、3つの配列が与えられるバージョンを使用します(wikiのThree different arraysを参照)。
サイズ $M$ の配列 $X, Y, Z$ が与えられる。$X_i + Y_j + Z_k = 0$ なる $(i, j, k)$ は存在するか？
帰着
サイズ $M = N^{2/3}$ の3-SUMのインスタンス $X, Y, Z$、および上記の数列の問題を $O(N^{1.333 - \epsilon})$ で解くsolverがあると仮定したときに、この 3-SUM が $O(M^{2 - \epsilon}) = O(N^{1.333 - \epsilon})$ 時間で解けることを示せばよい。
- $X$ を $N^{1/3}$ 回繰り返したサイズ $N$ の配列を用意し、数列の問題の初期値とする。
- $Y$ をサイズ $N^{1/3}$ の $N^{1/3}$ 個の配列に切り分け、それぞれについて下記の操作を行う。切り分けられた $Y$ を $Y'$ とする。
- 数列は$X$ を $N^{1/3}$ 回繰り返したものになっているのだが、加算クエリを用いて、$Y'$ の要素をそれぞれの$X$全体に足しこむ。これにより、数列には $x + y (x \in X, y \in Y')$ が全て現れる。
- $Z$ の各要素 $z$ について、数列に $-z$ が存在するかを判定する。これは3クエリ(全体 $+z$ → 調査クエリ → 全体 $-z$) で可能である。
- 足しこんだ $Y'$ の要素を引くことで、数列を初期値に戻す
クエリの回数はループの中の $-z$ 存在判定がボトルネックであり、$O(N^{1/3} \times N^{2/3}) = O(N)$ である。よって示された。
ギャップ
この数列の問題は平方分割で $O(N^{3/2})$ で解くことが出来ますが、$\Omega(N^{4/3})$ と$O(N^{3/2})$ の間にギャップが残っています。
値域
倍数クエリ のように、値域が $O(N)$ である (ので、平方分割がhashmapなしでも動作する) という出題例があります。
このような問題のために、この記事の数列の問題に「常に $|a_i| \le N$ であるようなクエリしかこない」という制約を加えた場合はどうなるでしょうか？ 実は今回の帰着はこの制約を加えるとうまくいきません。具体的には、値域が $O(N)$ の 3-SUM しか解けなくなってしまいます。そしてこれはそもそもFFTで $O(N \log N)$ で解けます。"値域が $O(N)$ の 3-SUM を解くぐらいには難しい"というそれなりに説得力のある(が、理論的には特に何も言っていない)事実は得られます。
感想
3-SUMや、$4/3$ が何か出てきたのが面白いですね。でもなんか $\Omega(N^{3/2})$ が示せるんじゃないのかなとは思っています。
