  The notions of synchronizing and partitioning sets are recently introduced
variants of locally consistent parsings with great potential in
problem-solving. In this paper we propose a deterministic algorithm that
constructs for a given readonly string of length $n$ over the alphabet
$\{0,1,\ldots,n^{\mathcal{O}(1)}\}$ a variant of $\tau$-partitioning set with
size $\mathcal{O}(b)$ and $\tau = \frac{n}{b}$ using $\mathcal{O}(b)$ space and
$\mathcal{O}(\frac{1}{\epsilon}n)$ time provided $b \ge n^\epsilon$, for
$\epsilon > 0$. As a corollary, for $b \ge n^\epsilon$ and constant $\epsilon >
0$, we obtain linear construction algorithms with $\mathcal{O}(b)$ space on top
of the string for two major small-space indexes: a sparse suffix tree, which is
a compacted trie built on $b$ chosen suffixes of the string, and a longest
common extension (LCE) index, which occupies $\mathcal{O}(b)$ space and allows
us to compute the longest common prefix for any pair of substrings in
$\mathcal{O}(n/b)$ time. For both, the $\mathcal{O}(b)$ construction storage is
asymptotically optimal since the tree itself takes $\mathcal{O}(b)$ space and
any LCE index with $\mathcal{O}(n/b)$ query time must occupy at least
$\mathcal{O}(b)$ space by a known trade-off (at least for $b \ge \Omega(n /
\log n)$). In case of arbitrary $b \ge \Omega(\log^2 n)$, we present
construction algorithms for the partitioning set, sparse suffix tree, and LCE
index with $\mathcal{O}(n\log_b n)$ running time and $\mathcal{O}(b)$ space,
thus also improving the state of the art.
