## 4 Our Data Structure for \(\epsilon\)-Approximate Counting
Note that the original \(\mathcal{C}_{I,\lambda,\kappa}\) is an ancestor of every \(\mathcal{C}_{J,\lambda,\kappa}\in\textsc{All}\), and in general, any \(\mathcal{C}_{H,\lambda,\kappa}\in\textsc{All}\) is an ancestor of every \(\mathcal{C}_{J,\lambda,\kappa}\in\textsc{All}\) with \(J\subset H\). We have the following lemma. (Note that we are abusing the notation here and regard \(\mathcal{D}^{Y}_{I,\epsilon}\) as a set.) **Lemma 5**: _Suppose that \(\mathcal{D}^{Y}_{I,\epsilon}=\langle\mathcal{C}_{J_{1},\lambda,\kappa},\ldots, \mathcal{C}_{J_{m},\lambda,\kappa}\rangle\) is covering \([p,r_{I}]\). Let \(\mathit{anc}(\mathcal{D}^{Y}_{I,\epsilon})=\mathit{anc}(\langle\mathcal{C}_{J_{1 },\lambda,\kappa},\ldots,\mathcal{C}_{J_{m},\lambda,\kappa}\rangle)\) be the set \(\big{\{}\mathcal{C}_{H,\lambda,\kappa}\mid\mathcal{C}_{H,\lambda,\kappa}\text{ is an ancestor of some }\mathcal{C}_{J_{i},\lambda,\kappa}\in\mathcal{D}^{Y}_{I,\epsilon}\big{\}}\). Then,_  
1. \(\textsc{All}_{\geq p}\subseteq\mathcal{D}^{Y}_{I,\epsilon}\cup\mathit{anc}( \mathcal{D}^{Y}_{I,\epsilon})\)_,__._
2. \(v_{\mathsf{add}}(\mathcal{C}_{J,\lambda,\kappa})\leq(1+\epsilon)Y\) _for any_ \(\mathcal{C}_{J,\lambda,\kappa}\in\textsc{All}\)_, and_
3. \(|\mathcal{D}^{Y}_{I,\epsilon}\cup\text{anc}(\mathcal{D}^{Y}_{I,\epsilon})|\leq 2 \log W\)_._  
_Therefore, \(\sum\{v_{\mathsf{add}}(\mathcal{C}_{J,\lambda,\kappa})\mid\mathcal{C}_{J, \lambda,\kappa}\in\textsc{All}_{\geq p}\}\leq 2(1+\epsilon)Y\log W\)._  
Proof. : For (1), it suffices to prove that for any \(\mathcal{C}_{J,\lambda,\kappa}\in\textsc{All}_{\geq p}\), \(\mathcal{C}_{J,\lambda,\kappa}\in\mathcal{D}^{Y}_{I,\epsilon}\cup\text{anc}( \mathcal{D}^{Y}_{I,\epsilon})\). By definition, \(J\) covers or is to the right of \(p\); thus \(J\cap(J_{1}\cup\cdots\cup J_{m})=J\cap[p,r_{1}]\
eq\emptyset\). Since the intervals are interesting and do not cross, there is an \(1\leq i\leq m\) such that either (i) \(J=J_{i}\), and thus \(\mathcal{C}_{J,\lambda,\kappa}\in\mathcal{D}^{Y}_{I,\epsilon}\), or (ii) \(J_{i}\subset J\), which implies \(\mathcal{C}_{J,\lambda,\kappa}\) is an ancestor of \(\mathcal{C}_{J_{i},\lambda,\kappa}\), _i.e._, \(\mathcal{C}_{J,\lambda,\kappa}\in\text{anc}(\mathcal{D}^{Y}_{I,\epsilon})\). (It is not possible that \(J\subset J_{i}\); otherwise \(\mathcal{C}_{J_{i},\lambda,\kappa}\) would have been split and should not be in the current \(\mathcal{D}^{Y}_{I,\epsilon}\). Hence, \(\mathcal{C}_{J,\lambda,\kappa}\in\mathcal{D}^{Y}_{I,\epsilon}\cup\text{anc}( \mathcal{D}^{Y}_{I,\epsilon})\). To prove (2), suppose that \(J=[x,y]\) and \(v_{\mathsf{add}}(\mathcal{C}_{J,\lambda,\kappa})\) has just reached \((1+\epsilon)Y\). This implies \(f_{*}([x,r_{I}])\geq(1+\epsilon)Y\), and so does its estimate \(\hat{f}_{*}([x,r_{I}])\) given by \(\mathcal{B}_{I,\epsilon}\) (as \(f_{*}([x,r_{I}])\leq\hat{f}_{*}([x,r_{I}])\), by Equation (7)). Then, the procedure \(\text{Trim}(\,)\) will be called and \(\mathcal{C}_{J,\lambda,\kappa}\) will be either thrown away or split, and no more value can be added to \(\mathcal{C}_{J,\lambda,\kappa}\). It follows that \(v_{\mathsf{add}}(\mathcal{C}_{J,\lambda,\kappa})\leq(1+\epsilon)Y\). For (3), recall that \(\mathcal{D}^{Y}_{I,\epsilon}=\langle\mathcal{C}_{J_{1},\lambda,\kappa}, \mathcal{C}_{J_{2},\lambda,\kappa},\ldots\mathcal{C}_{J_{m},\lambda,\kappa}\rangle\). Among the intervals \(J_{1},\ldots,J_{m}\), interval \(J_{1}\) is the leftmost interval and its left boundary \(\ell_{J_{1}}=p\). We now prove that \(\mathcal{D}^{Y}_{I,\epsilon}\cup\text{anc}(\mathcal{D}^{Y}_{I,\epsilon})= \mathcal{D}^{Y}_{I,\epsilon}\cup\text{anc}(\mathcal{C}_{J_{1},\lambda,\kappa})\) where \(\text{anc}(\mathcal{C}_{J_{1},\lambda,\kappa})\) is the set of ancestors of \(\mathcal{C}_{J_{1},\lambda,\kappa}\).