Which axis are you prefixing?
Count values in a numeric interval or letters inside a substring.
Prefixes over possible values
A query asking how many observations have values in [L, R] is different from a query about positions [L, R]. Build freq[0..U], then C[0] = 0 and C[v + 1] = C[v] + freq[v]. C[t] counts observations with value strictly below t.
The inclusive value-range answer is C[R + 1] − C[L]. Allocate U + 2 prefix entries so value zero and the upper endpoint are both handled. For [3, 0, 3, 5, 1, 3], value interval [1, 3] contains four observations wherever they occurred.
Prefixes over positions, with one column per letter
A whole-word letter table forgets arrangement: aabb and bbaa have equal overall counts but different first-two-character counts. Preserve position information with P[i][c] = count of letter c in the first i characters.
Copy row i − 1 into row i, then increment the column for text[i − 1]. A query for letter c in inclusive positions [l, r] is P[r][c] − P[l − 1][c]. Starting every row from zero would store only one character instead of the cumulative prefix.
// Complete C++23 program. Input: lowercase ASCII word q, then l r letter.
#include <iostream>
#include <string>
#include <vector>
int main() {
std::string text;
int q;
std::cin >> text >> q;
int n = static_cast<int>(text.size());
std::vector<std::vector<int>> pref(n + 1, std::vector<int>(26, 0));
for (int i = 1; i <= n; ++i) {
pref[i] = pref[i - 1];
++pref[i][text[i - 1] - 'a'];
}
while (q--) {
int l, r;
char c;
std::cin >> l >> r >> c;
int id = c - 'a';
std::cout << pref[r][id] - pref[l - 1][id] << '\n';
}
}Columns cost memory and time
With alphabet size σ, copying every row costs O(σn), storage is O(σn), and a query about one letter costs O(1). For 26 letters and 100000 characters, raw four-byte counts alone occupy about 10.4 MB, before vector-row overhead.
Do not extend one prefix column per key to an enormous alphabet automatically. Storing sorted occurrence positions for each value and using two binary searches is another representation, connecting to Session 5’s map of vectors.
Frequency array
The value becomes an index. Each arrival increases freq[value] by one. This domain has ten possible values.
Input values
freq[value] — indices are values
The frequencies add up to 6, the number of input values.
Guided simulation · Change the inputs to test your understanding.
For C[t] = number of observations with value < t, what does C[4] − C[1] count?
Turn the idea into code
In abacaba, count a in positions [2, 6], b in [1, 7], and a in [4, 4]. Explain the zero-based character conversion.
Give me a hint
Write positions 1 through 7 above the letters. A prefix row i consumes text[i − 1].
Show the explained solution
The answers are 2, 2, and 0. The a occurrences in [2,6] are positions 3 and 5; b occurs at 2 and 6; position 4 is c. Convert the one-based character position i to string index i − 1 only when reading the character.
Your notes
Mark complete when you can explain it yourself.