Rank query
= Rank query
{title2=$\operatorname{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.