Problem Detail: 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
Asked By : Erric
Answered By : Yuval Filmus
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/34099 Ask a Question Download Related Notes/Documents
