We present computationally efficient centralized and distributed moving horizon estimation (MHE) methods for large-scale interconnected systems, that are described by sparse banded or sparse multibanded system matrices. Both of these MHE methods are developed by approximating a solution of the MHE problem using the Chebyshev approximation method. By exploiting the sparsity of this approximate solution we derive a centralized MHE method, which computational complexity and storage requirements scale linearly with the number of local subsystems of an interconnected system. Furthermore, on the basis of the approximate solution of the MHE problem, we develop a novel, distributed MHE method. This distributed MHE method estimates the state of a local subsystem using only local input-output data. In contrast to the existing distributed algorithms for the state estimation of large-scale systems, the proposed distributed MHE method is not relying on the consensus algorithms and has a simple analytic form. We have studied the stability of the proposed MHE methods and we have performed numerical simulations that confirm our theoretical results.