Binary Decomposition

Binary decomposition often refers to processing bits of an index or value (Fenwick/BIT intuition). For interviews, know how powers of two partition ranges.

Try this in Python

def powers_of_two_sum_to(n: int) -> list[int]:
    """Greedy collect largest power <= remaining (related to binary representation idea)."""
    parts: list[int] = []
    while n > 0:
        p = 1
        while p * 2 <= n:
            p *= 2
        parts.append(p)
        n -= p
    return parts


print(powers_of_two_sum_to(13))

Key takeaways

• Connect to binary representation of integers.
• Not every problem needs Fenwick tree; start with bit meaning.
• Practice small n by hand.