A character rank query asks how many occurrences of character appear in the first 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.
New to topics? Read the docs here!