Can anyone give me a proof as to why

Any range over a unviverse {1...n} can be reduced to at most $2log_2n$ disjoint dyadic ranges?

Where a dyadic range is a range of the form $[x2^y+1....(x+1)2^y]$.

This is in reference to the method for answering range queries with a Count-Min Sketch as mentioned in the original paper on CM-sketches

Here is proof by example: \begin{align*} &[0110000,1101011] = \\ &[0110000,0110000] \cup \\ &[0110001,1000000] \cup \\ &[1000001,1100000] \cup \\ &[1100001,1101000] \cup \\ &[1101001,1101010] \cup \\ &[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 < 2^{k+1}$ (one of the ranges can be empty). Writing $b = 2^k + 2^{t_0} + \cdots + 2^{t_d}$, where $k > t_0 > \cdots > 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.
• This seems to be the right way to go about it, and although I'm very much convinced that it can certainly be decomposed, my doubt is about the bound $2log_2n$. Could you point out when I would be needing $2log_2n$? Dec 10 '14 at 7:19
• You need at most $\log_2 n$ to decompose each of the two halves. Here $\log_2 n$ is the maximal number of 1s in the binary representation. The bound can probably be improved slightly, though it shouldn't be hard to find examples which need $2\log_2 n - C$ ranges, for some small constant $C$. Dec 10 '14 at 7:23