We study the full distribution $P_M(S)$ of the number of distinct sites $S$ visited by a random walker on a $d$-dimensional lattice after $M$ steps. We focus on the case $d \ge 2$, and we are interested in the long-time limit $M \gg 1$. Our primary interest is the behavior of the right and left tails of $P_M(S)$, corresponding to $S$ larger and smaller than its mean value, respectively. We present theoretical arguments that predict that in the right tail, a standard large-deviation principle (LDP) $P_{M}\left(S\right)\sim e^{-MΦ\left(S/M\right)}$ is satisfied (at $M \gg 1$) for $d\ge2$, while in the left tail, the scaling behavior is $P_{M}\left(S\right)\sim e^{-M^{1-2/d}Ψ\left(S/M\right)}$, corresponding to a LDP with anomalous scaling, for $d>2$. We also obtain bounds for the scaling functions $Φ(a)$ and $Ψ(a)$, and obtain analytical results for $Φ(a)$ in the high-dimensional limit $d \gg 1$, and for $Ψ(a)$ in the limit $a \ll 1$ (describing the far left tail). Our predictions are validated by numerical simulations using importance sampling algorithms.