Position Mapping

When we descend from a node to its child, you need to map positions.

If you're tracking range $[l, r]$ at a node, and we go left (to elements with bit 0):

• New left index: $\text{rank}_0(B, l)$
• New right index: $\text{rank}_0(B, r + 1) - 1$

Going right (to elements with bit 1):

• New left index: $\text{rank}_1(B, l)$
• New right index: $\text{rank}_1(B, r + 1) - 1$

This mapping is the core of all wavelet tree queries. It tells us which positions in the child correspond to your query range.