The Dynamic k-Mismatch Problem

First, we describe a simple data structure with Õ(1) update time and Õ(k) query time. Through considerably more sophisticated techniques, we show that Õ(k) update time and Õ(1) query time is also achievable. These two solutions likely provide an essentially optimal trade-off for the dynamic k-mismatch problem with m^{Ω(1)} ≤ k ≤ \sqrt{m}: we prove that, in that case, conditioned on the 3SUM conjecture, one cannot simultaneously achieve k^{1-Ω(1)} time for all operations (updates and queries) after n^{O(1)}-time initialization. For k ≥ \sqrt{m}, the same lower bound excludes achieving m^{1/2-Ω((1)} time per operation. This is known to be essentially tight for constant-sized alphabets: already Clifford et al. (STACS 2018) achieved Õ(\sqrt{m}) time per operation in that case, but their solution for large alphabets costs Õ(m^{3/4}) time per operation. We improve and extend the latter result by developing a trade-off algorithm that, given a parameter 1 ≤ x ≤ k, achieves update time Õ(\frac{m}{k} +\sqrt{\frac{mk}{x}}) and query time Õ(x). In particular, for k ≥ \sqrt{m}, an appropriate choice of x yields Õ(\sqrt[3]{mk}) time per operation,
which is Õ(m^{2/3}) when only the trivial threshold k=m is provided.