This paper considers moving horizon estimation (MHE) approach to solution of staged quadratic programming (QP) problems. Using an insight into the constrained solution structure for the growing horizon, we develop a very accurate iterative update of the arrival cost in the MHE solution. The update uses a quadratic approximation of the arrival cost and information about the previously active or inactive constraints. In the absence of constraints, the update is the familiar Kalman filter in information form. In the presence of the constraints, the update requires solving a sequence of linear systems with varying size. The proposed MHE update provides very good performance in numerical examples. This includes problems with l 1 regularization where optimal estimation allows us to perform online segmentation of streaming data.