 Dyadic decomposition

A dyadic decomposition partitions a positive range into intervals $(M,2M]$. It reduces a variable-length sum to $O(\log N)$ sums in which every variable has a fixed order of magnitude.