## 5 Reducing the Size of \(\mathcal{D}^{Y}_{I,\epsilon}\)
Note that  
* the consolidation step will added at most \(\lambda\) units to \(v(N_{h})\) before we move on to consider the node immediately to its right, and
* for node \(N_{i}\) with \(i\geq h+1\), any node \(N\) that has been merged to \(N_{i}\) must be to the right of of \(N_{h}\), and thus is to the right of \(t\); it follows that \(N\) is contributing \(v(N)\) to \(v(\mathsf{alive}(\mathcal{E}^{Y}_{I,\epsilon})_{\geq t}^{a})\) in Equation (10) and its merging will not make any change. In conclusion, the consolidation steps introduce at most \(\lambda\) extra errors, and Equation (10) becomes \(v(\mathsf{alive}(\mathcal{E}^{Y}_{I,\epsilon})_{\geq t}^{a})\leq f_{a}([t,r_{ I}])+\lambda\log W+\lambda\leq f_{a}([t,r_{I}])+2\epsilon Y\), which is the second inequality of the lemma. To prove the first inequality, suppose that we ask for the estimate \(\hat{f}_{a}([t,r_{I}])\) during the \(i\)th period, when we have \(\mathcal{C}_{I_{1..i-2},\lambda,\frac{1}{\epsilon}}\), \(\mathcal{D}^{Y}_{I_{i-1},\epsilon}\) and \(\mathcal{D}^{Y}_{I_{i},\epsilon}\). Recall that \(\mathcal{C}_{I_{1..i-2},\lambda,\epsilon}\) comes from consolidating \(\mathcal{D}^{Y}_{I_{1},\epsilon},\mathcal{D}^{Y}_{I_{2},\epsilon},\dots,\mathcal{ D}^{Y}_{I_{i-2},\epsilon}\). As in all our previous analyses, we have  
\[f_{a}([t,r_{I}])-v(\mathsf{alive}(\mathcal{E}^{Y}_{I,\epsilon})_{\geq t}^{a}) \leq v(\mathsf{node}(\mathcal{E}^{Y}_{I,\epsilon})_{\geq t}^{a})-v(\mathsf{ alive}(\mathcal{E}^{Y}_{I,\epsilon})_{\geq t}^{a})=d(\mathsf{dead}(\mathcal{E}^{Y}_{I, \epsilon})_{\geq t}^{a})\]  
(Note that the merging of nodes during consolidations would not take away any value). To get a bound on \(d(\mathsf{dead}(\mathcal{E}^{Y}_{I,\epsilon})_{\geq t}^{a})\), suppose that \(p_{\mathtt{max}}\in I_{k}\). Then, all the nodes to the left of \(I_{k}\) have been thrown away. Among \(\mathcal{D}^{Y}_{I_{k},\epsilon},\mathcal{D}^{Y}_{I_{k+1},\epsilon},\dots, \mathcal{D}^{Y}_{I_{m},\epsilon}\), only \(\mathcal{D}^{Y}_{I_{k},\epsilon}\) may have been trimmed. Note that * \(d(\mathsf{dead}(\mathcal{E}^{Y}_{I_{\epsilon},\epsilon})_{\geq t}^{a})\leq d( \mathsf{dead}(\mathcal{D}^{Y}_{I_{k},\epsilon})_{\geq\mathsf{Pmax}}^{a})+\sum_{k +1\leq\epsilon\leq m}d(\mathsf{dead}(\mathcal{D}^{Y}_{I_{\epsilon},\epsilon})^{a})\),
* as in the proof of Theorem 7, we can argue that \(d(\mathsf{dead}(\mathcal{D}^{Y}_{I_{k},\epsilon})_{\geq\mathsf{Pmax}}^{a}) \leq\epsilon Y\), and
* for the other \(\mathcal{D}^{Y}_{I_{\epsilon},\epsilon}\), since their capacity is at least \(\frac{1}{\epsilon}\) \[\sum_{k+1\leq\ell\leq m}d(\mathsf{dead}(\mathcal{D}^{Y}_{I_{\epsilon},\epsilon })^{a})\leq\sum_{k+1\leq\ell\leq m}f_{*}(I_{\ell})/(1/\epsilon)\leq\epsilon f_ {*}([p_{\mathsf{max}}+1,r_{I}])\leq\epsilon Y\]  
Thus, \(d(\mathsf{dead}(\mathcal{E}^{Y}_{I_{\epsilon},\epsilon})_{\geq t}^{a}))\leq 2 \epsilon Y\), and the first inequality follows. For Statement (2), note that both \(\mathcal{D}^{Y}_{I_{i-1},\epsilon}\) and \(\mathcal{D}^{Y}_{I_{i},\epsilon}\) have size \(O(\frac{1}{\epsilon}\log\log d_{\max}\log d_{\max})\) (by Theorem 7, and \(|I_{i-1}|=|I_{i}|=d_{\max}\)), and for \(\mathcal{C}_{J_{1..i-2},\lambda,\frac{1}{\epsilon}}\), it has size \(O(Y/\lambda+\frac{1}{\epsilon})=O(\frac{1}{\epsilon}\log d_{\max})\); thus the size of \(\mathcal{E}^{Y}_{I,\epsilon}\) is \(O(\frac{1}{\epsilon}\log\log d_{\max}\log d_{\max})\). For the update time, it suffices to note that it is dominated by the update times of \(\mathcal{D}^{Y}_{I_{i-1},\epsilon}\) and \(\mathcal{D}^{Y}_{I_{i},\epsilon}\).