  The territory explored by a random walk is a key property that may be
quantified by the number of distinct sites that the random walk visits up to a
given time. The extent of this spatial exploration characterizes many important
physical, chemical, and ecological phenomena. In spite of its fundamental
interest and wide utility, the number of visited sites gives only an incomplete
picture of this exploration. In this work, we introduce a more fundamental
quantity, the elapsed time $\tau_n$ between visits to the $n^{\rm th}$ and the
$(n+1)^{\rm st}$ distinct sites, from which the full dynamics about the
visitation statistics can be obtained. To determine the distribution of these
inter-visit times $\tau_n$, we develop a theoretical approach that relies on a
mapping with a trapping problem, in which, in contrast to previously studied
situations, the spatial distribution of traps is continuously updated by the
random walk itself. Despite the geometrical complexity of the territory
explored by a random walk (typically aspherical, as well as containing holes
and islands at all scales), we find that the distribution of the $\tau_n$ can
be accounted for by simple analytical expressions. Processes as varied as
regular diffusion, anomalous diffusion, and diffusion in disordered media and
fractals, fall into the same universality classes for the temporal history of
distinct sites visited. We confirm our theoretical predictions by Monte Carlo
and exact enumeration methods. We also determine additional basic exploration
observables, such as the perimeter of the visited domain or the number of
islands of unvisited sites enclosed within this domain, thereby illustrating
the generality of our approach. Because of their fundamental character and
their universality, these inter-visit times represent a promising tool to
unravel many more aspects of the exploration dynamics of random walks.
