Count-Min sketch: dyadic ranges
Here is proof by example:
$$
\begin{align*}
&amp;[0110000,1101011] = \\
&amp;[0110000,0110000] \cup \\
&amp;[0110001,1000000] \cup \\
&amp;[1000001,1100000] \cup \\
&amp;[1100001,1101000] \cup \\
&amp;[1101001,1101010] \cup \\
&amp;[1101011,1101011]
\end{align*}
$$
More generally, the first step is to decompose your range $[a,b]$ into $[a,2^k] \cup [2^k+1,b]$, where $b &lt; 2^{k+1}$ (one of the ranges can be empty). Writing $b = 2^k + 2^{t_0} + \cdots + 2^{t_d}$, where $k &gt; t_0 &gt; \cdots &gt; t_d$, we decompose $[2^k+1,b]$ as follows:
$$
[2^k+1,b] = [2^k+1, 2^k+2^{t_0}] \cup [2^k+2^{t_0}+1,2^k+2^{t_0}+2^{t_1}] \cup \cdots \cup [2^k + 2^{t_0} + \cdots + 2^{t_{d-1}}+1, 2^k + 2^{t_0} + \cdots + 2^{t_d}].
$$
Decomposing $[a,2^k]$ into dyadic ranges is similar but slightly more confusing, and I leave it to you.