区間add / 0存在判定 Ω(N^(1.333)) - よすぽの日記 を公開したらhosさんからΩ*(N1.5)の証明が届いたので紹介します。前記事を読んでいることを前提とします。 Conv 3-SUM 3-SUMの wiki の Convolution sumとして紹介されているvariant(の、3array版)を考えま…

UPD: 区間add / 0存在判定 Ω*(N^(1.5)) - よすぽの日記 太古に考え、メモってなかったのですが、最近思い出そうとして苦労したのでメモっておきます。 問題 以下の問題の計算量下界について考えます。 長さ $N$ の数列 $a_1, \cdots, a_N$ が与えられる。$N$…