Rank query (${\mathrm{rank}}_c(r)$)

A character rank query asks how many occurrences of character $c$ appear in the first $r$ positions of a sequence. A prefix sum array answers a single-character version in constant time after linear preprocessing; a wavelet tree supports many characters more compactly.