The impact of parameter variations on timing has become significant in recent years. Existing statistical timing analysis (STA) tools either suffer from high computational complexity or significant errors when timing variables become correlated. In this paper, we present an efficient algorithm to predict the probability distribution of the circuit delay while accounting for spatial correlations. We exploit the structure of the covariance matrix to decouple the correlated variables to independent ones in linear-time, as opposed to conventional techniques which have a cubic-time complexity. Furthermore, we present a closed-form expression for the probability distribution of the {\tt max} operation, based on which we propose a fast and accurate approximation technique. Experiments show that the proposed method is both accurate and efficient.