Frequency of given number in range[a,b]

So, there’s a question I was solving questions on prefix sum Question Couldn’t come up with a better idea than O(q*n) where q= Number of Queries and N= Number of Array elements.
Can you help me? I don’t have much idea about segment tree, please use the simple way.

You are given an array of N numbers, each a number between 1 and 10.

You need to answer Q queries, each specified by a, b, c, and asking how many times the number c appears between position a and position b, inclusive.

Since the largest test case is very large, you will need to use efficient input and output mechanism in your chosen language.

Since every number is between 1 and 10 inclusive, use 2-D Array.
Code.

#include <stdio.h>
#include <string.h>
int main() {
    int n, q;
    scanf("%d %d", &n, &q);
    int a[n];
    for(int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    int freq[11][n + 1];
    memset(freq, 0, sizeof(freq));
    for(int i = 0; i < 11; i++) {
        for(int j = 1; j < n + 1; j++) {
            freq[i][j] = freq[i][j-1] + (a[j-1] == i ? 1 : 0);
        }
    }
    for(; q > 0; q--) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        printf("%d\n", freq[c][b] - freq[c][a-1]);
    }
    return 0;
}
2 Likes

would you please explain those loops, what exactly you’re doing there?

1 Like

It’s basically building prefix sum. Say the array is:

1 1 2 3 2 1 3 4 1 3 2 2 1 1 5 1 2 1 3

The Array representing the Prefix sum of individual elements looks like this.

Scanning Elements.

Represents the above image.

Filling all the cells with 0.

Since all values lie between 1 and 10 inclusive, we iterate from 0 to 10 ( 1 to 10 is enough actually).

Iterate over the array elements to fill i^{th} row of values as shown in the image.

Answer the queries, each one in O(1).

Overall time complexity: O(N * 10) for building table + O(Q) for queries.

2 Likes