Lightweight estimation of $\sum_{i=0}^n \gamma(i)$, the sum of the auto-covariances Suppose $X_1,\cdots,X_n$ are samples from a stationary time series and let $\gamma(i)$ denote the autocovariance $\gamma(i) = \mathrm{Cov}(X_{k},X_{k+i})$. Suppose $n$ is very large.
In a numerical method I am working on, the quantity $\sum_{i=0}^n \gamma(i)$ appears all the time. I am looking for a quick/lightweight way to guess/estimate this quantity from the data without computing $\sum_{i=0}^n \hat\gamma(i)$ because this is tedious for large $n$ (here $\hat\gamma(i)$ denote the sample autocovariance). It has to do the estimation in $O(n)$ time. Does there exist such a method/trick/insight?
 A: Let $\dot X_i=X_i-\bar X$.  Using the definition of the sample autocovariance function and rearranging the resulting double sum yields
\begin{align}
\sum_{k=0}^{n-1}\hat\gamma_k
  &=\sum_{k=0}^{n-1}\left(\frac1n\sum_{i=1}^{n-k}\dot X_i \dot X_{i+k}\right)
\\&=\frac1n \sum_{i=1}^n \sum_{j=1}^i \dot X_i \dot X_j
\\&=\frac1n \sum_{i=1}^n \left(\dot X_i \sum_{j=1}^i \dot X_j\right).
\end{align}
For example, for $n=3$ the sum can be written as
$$
\frac13(\dot X_1 \dot X_1 + \dot X_2 (\dot X_1 + \dot X_2) + \dot X_3 (\dot X_1 + \dot X_2 + \dot X_3).
$$
This can be computed in $O(n)$ time without any nested for-loops by adding $\dot X_i$ to the last stored value of the inner sum to get its new value.  This can be implemented in R using for-loops as
sumacf <- function(x) { 
  x <- x - mean(x)
  n <- length(x)
  innersum <- 0
  outersum <- 0
  for (i in 1:n) {
    innersum <- innersum + x[i]
    outersum <- outersum + x[i]*innersum
  }
  1/n*outersum
}

or, more efficiently, as
sumacf <- function(x) {
  x <- x - mean(x)
  mean(x*cumsum(x))
}

A small test against R's acf function to verify that this works:
> x <- rnorm(10)
> sumacf(x)
[1] 0.610785
> sum(acf(x,type="covariance")$acf)
[1] 0.610785

