## 4 Our Data Structure for \(\epsilon\)-Approximate Counting
Then, together with the facts that \(|\mathcal{D}^{Y}_{I,\epsilon}|\leq\log W\) (by Property (ii) of interesting-partition) and \(|\text{anc}(\mathcal{C}_{J_{1},\lambda,\kappa})|\leq\log W\) (as each Split operation would reduce the size of interval by half), we have  
\[|\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}) |\leq|\mathcal{D}^{Y}_{I,\epsilon}|+|\text{anc}(\mathcal{C}_{J_{1},\lambda, \kappa})|\leq 2\log W\]  
To show \(\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})\), it suffices to show that for any \(\mathcal{C}_{H,\lambda,\kappa}\in\text{anc}(\mathcal{D}^{Y}_{I,\epsilon})\), \(\mathcal{C}_{H,\lambda,\kappa}\in\text{anc}(\mathcal{C}_{J_{1},\lambda,\kappa})\). Since \(\mathcal{C}_{H,\lambda,\kappa}\in\text{anc}(\mathcal{D}^{Y}_{I,\epsilon})\), it is the ancestor of some \(\mathcal{C}_{J_{i},\lambda,\kappa}\in\mathcal{D}^{Y}_{I,\epsilon}\). Thus \(J_{i}=[\ell_{J_{i}},r_{J_{i}}]\subset H=[\ell_{H},r_{H}]\). Since \(\mathcal{C}_{H,\lambda,\kappa}\) is already an ancestor, it no longer exists, and all the \(\mathcal{C}_{J,\lambda,\kappa}\) to its left have been thrown away. Thus, \(\mathcal{D}^{Y}_{I,\epsilon}\) has no \(\mathcal{C}_{J,\lambda,\kappa}\) where \(J\) is to the right of \(\ell_{H}\). This implies \(\ell_{H}\leq p=\ell_{J_{1}}\) and \(\ell_{H}\leq\ell_{J_{1}}\leq r_{J_{1}}\leq r_{J_{i}}\leq r_{H}\). It follows that \(J_{1}\subset H\) and \(\mathcal{C}_{H,\lambda,\kappa}\) is an ancestor of \(\mathcal{C}_{J_{1},\lambda,\kappa}\), _i.e._, \(\mathcal{C}_{H,\lambda,\kappa}\in\text{anc}(\mathcal{C}_{J_{1},\lambda,\kappa})\). We are now ready to analyze the accuracy of \(\mathcal{D}^{Y}_{I,\epsilon}\)'s estimates. **Theorem 6**: _Suppose that \(\mathcal{D}^{Y}_{I,\epsilon}\) is covering \([p,r_{I}]\). For any item \(a\) and any \(t\in[p,r_{I}]\), the estimate \(\hat{f}_{a}([t,r_{I}])\) of \(f_{a}([t,r_{I}])\) obtained by \(\mathcal{D}^{Y}_{I,\epsilon}\) satisfies \(|\hat{f}_{a}([t,r_{I}])-f_{a}([t,r_{I}])|\leq\epsilon Y\). Furthermore, \(\mathcal{D}^{Y}_{I,\epsilon}\) uses \(O(\frac{1}{\epsilon}(\log W)^{2})\) space._  
Proof. : Let \(\mathsf{alive}(\mathcal{D}^{Y}_{I,\epsilon})\) be the set of nodes currently in \(\mathcal{D}^{Y}_{I,\epsilon}\), \(\mathsf{dead}(\mathcal{D}^{Y}_{I,\epsilon})\) the set of those that were in \(\mathcal{D}^{Y}_{I,\epsilon}\) earlier in the execution but have been deleted, and \(\mathsf{node}(\mathcal{D}^{Y}_{I,\epsilon})=\mathsf{alive}(\mathcal{D}^{Y}_{I, \epsilon})\cup\mathsf{dead}(\mathcal{D}^{Y}_{I,\epsilon})\). It can be verified that \(\hat{f}_{a}([t,r_{I}])=v(\mathsf{alive}(\mathcal{D}^{Y}_{I,\epsilon})_{ \geq t}^{a})\). Below, we prove that  
\[f_{a}([t,r_{I}])-\tfrac{2(1+\epsilon)Y}{\kappa}\log W\leq v(\mathsf{alive}( \mathcal{D}^{Y}_{I,\epsilon})_{\geq t}^{a})\leq f_{a}([t,r_{I}])+\lambda\log W \tag{8}\]  
Recall that we fix \(\lambda=\epsilon Y/\log W\) and \(\kappa=\frac{4}{\epsilon}\log W\); the \(\epsilon Y\) error bound follows. The proof of the second inequality of Equation (8) is identical to that of Lemma 3, except that we replace all occurrences of \(\mathcal{C}_{I,\lambda,\kappa}\) by \(\mathcal{D}^{Y}_{I,\epsilon}\). The proof of the first inequality is also similar. We still have  
\[f_{a}([t,r_{I}])-v(\mathsf{alive}(\mathcal{D}^{Y}_{I,\epsilon})_{\geq t}^{a}) \leq v(\mathsf{node}(\mathcal{D}^{Y}_{I,\epsilon})_{\geq t}^{a})-v(\mathsf{ alive}(\mathcal{D}^{Y}_{I,\epsilon})_{\geq t}^{a})=v(\mathsf{dead}(\mathcal{D}^{Y}_{I, \epsilon})_{\geq t}^{a})\]which equals \(d(\mathsf{dead}(\mathcal{D}^{Y}_{I,\epsilon})_{\geq t}^{a})\). As in Lemma 3, we can derive the bound \(d(\mathsf{dead}(\mathcal{D}^{Y}_{I,\epsilon})_{\geq t}^{a})\leq\frac{1}{\kappa}v( \mathsf{node}(\mathcal{D}^{Y}_{I,\epsilon}))=\frac{1}{\kappa}f_{*}(I)\), but we can do better here.