  We consider the Modular Subset Sum problem: given a multiset $X$ of integers
from $\mathbb{Z}_m$ and a target integer $t$, decide if there exists a subset
of $X$ with a sum equal to $t \pmod{m}$. Recent independent works by Cardinal
and Iacono (SOSA'21), and Axiotis et al. (SOSA'21) provided simple and
near-linear algorithms for this problem. Cardinal and Iacono gave a randomized
algorithm that runs in $O(m \log m)$ time, while Axiotis et al. gave a
deterministic algorithm that runs in $O(m \text{ polylog } m)$ time. Both
results work by reduction to a text problem, which is solved using a dynamic
strings data structure.
  In this work, we develop a simple data structure, designed specifically to
handle the text problem that arises in the algorithms for Modular Subset Sum.
Our data structure, which we call the shift-tree, is a simple variant of a
segment tree. We provide both a hashing-based and a deterministic variant of
the shift-trees.
  We then apply our data structure to the Modular Subset Sum problem and obtain
two algorithms. The first algorithm is randomized and matches the $O(m \log m)$
runtime of the algorithm by Cardinal and Iacono. The second algorithm is fully
deterministic and runs in $O(m \log m \cdot \alpha(m))$ time, where $\alpha$ is
the inverse Ackermann function.
