Static Range Queries allow us to gather information from arrays without updating them.

🔢 1. Frequency Arrays

🎯 Problem: Count the occurrences of each element in an array.

❌ Naive Approach:

• Loop through the array for each query → O(N^2).

✅ Efficient Approach:

• Build a frequency array → O(N) to build, O(1) per query.

🧠 Idea: Each index in the frequency array represents the value of the element. The value at that index represents its count.

🧪 Example:

A = [8, 5, 4, 6, 5, 8, 5, 4, 2]
Freq = [0, 0, 1, 0, 2, 3, 1, 0, 2]

📌 Query Examples:

• Freq[5] = 3 → appears 3 times
• Freq[8] = 2
• Freq[2] = 1
• Freq[7] = 0 → doesn’t exist

💻 Code:

const int MAX_VAL = 1e6 + 1;
int main() {
    int n, Freq[MAX_VAL] = {};
    cin >> n;
    vector<int> A(n);
    for (int i = 0; i < n; ++i) {
        cin >> A[i];
        Freq[A[i]]++;
    }
    for (int i = 0; i < n; ++i) {
        if (Freq[A[i]] > 0) {
            cout << "Frequency of " << A[i] << " is " << Freq[A[i]] << ".\\\\n";
            Freq[A[i]] = 0;
        }
    }
}

📝 Notes:

• Index must represent the possible values → integers only.