Truy vấn đếm phần tử mảng có giá trị trong khoảng cho trước trong C++

Trong bài toán này, ta được cho mảng arr[] và Q truy vấn, mỗi truy vấn có thể là một trong hai loại:

• {1, L, R} – Đếm số phần tử mảng có giá trị trong khoảng [L, R].
• {2, index, val} – Cập nhật phần tử tại index thành val.

Nhiệm vụ: tạo chương trình giải quyết truy vấn đếm phần tử mảng có giá trị trong khoảng cho trước trong C++.

Ví dụ minh họa

Đầu vào: arr[] = {1, 5, 2, 4, 2, 2, 3, 1, 3}

Q = 3

Query = { {1, 4, 8}, {2, 6, 5}, {1, 1, 4} }

Đầu ra: 3 7

Giải thích

Truy vấn 1: đếm phần tử trong khoảng [4, 8]. Kết quả = 1 (chỉ có 5).

Truy vấn 2: cập nhật arr[6] = 5. Mảng mới: {1, 5, 2, 4, 2, 2, 5, 1, 3}

Truy vấn 3: đếm phần tử trong khoảng [1, 4]. Kết quả = 7.

Phương pháp giải

Cách đơn giản: duyệt mảng trực tiếp, đếm phần tử thỏa mãn L ≤ phần tử ≤ R.

Ví dụ

#include <iostream>
using namespace std;

int countElementInRange(int arr[], int N, int L, int R) {
    int ValueCount = 0;
    for (int i = 0; i < N; i++) {
        if (arr[i] >= L && arr[i] <= R)
            ValueCount++;
    }
    return ValueCount;
}

int main() {
    int arr[] = {1, 5, 2, 4, 2, 2, 3, 1, 3};
    int N = sizeof(arr) / sizeof(arr[0]);
    int Q = 3;
    int query[Q][3] = { {1, 4, 8}, {2, 6, 5}, {1, 1, 4} };
    for(int i = 0; i < Q; i++) {
        if(query[i][0] == 1)
            cout << "The count of array elements with value in given range is "
                 << countElementInRange(arr, N, query[i][1], query[i][2]) << endl;
        else if(query[i][0] == 2) {
            cout << "Updating Value \n";
            arr[query[i][1]] = query[i][2];
        }
    }
    return 0;
}

Đầu ra

The count of array elements with value in given range is 2
Updating Value
The count of array elements with value in given range is 7

Độ phức tạp O(Q×N).

Cách tốt hơn: dùng Binary Indexed Tree (Fenwick Tree). Lưu tần suất giá trị phần tử vào cây, dùng getSum để tính số phần tử trong khoảng giá trị.

ElementCount[L, R] = getSum(R) - getSum(L - 1)

Ví dụ

#include <iostream>
using namespace std;

class BinaryIndTree {
public:
    int* BIT;
    int N;
    BinaryIndTree(int N) {
        this->N = N;
        BIT = new int[N];
        for (int i = 0; i < N; i++) BIT[i] = 0;
    }
    void update(int index, int increment) {
        while (index < N) {
            BIT[index] += increment;
            index += (index & -index);
        }
    }
    int calcSum(int index) {
        int sum = 0;
        while (index > 0) {
            sum += BIT[index];
            index -= (index & -index);
        }
        return sum;
    }
};

void UpdateValue(int* arr, int n, int index, int val, BinaryIndTree* fenwickTree) {
    int removedElement = arr[index];
    fenwickTree->update(removedElement, -1);
    arr[index] = val;
    fenwickTree->update(val, 1);
}

int countElementInRange(int* arr, int n, int L, int R, BinaryIndTree* fenwickTree) {
    return fenwickTree->calcSum(R) - fenwickTree->calcSum(L - 1);
}

int main() {
    int arr[] = { 1, 5, 2, 4, 2, 2, 3, 1, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int Q = 3;
    int query[Q][3] = { {1, 4, 8}, {2, 6, 5}, {1, 1, 4} };
    int N = 100001;
    BinaryIndTree* fenwickTree = new BinaryIndTree(N);
    for (int i = 0; i < n; i++)
        fenwickTree->update(arr[i], 1);
    for(int i = 0; i < Q; i++) {
        if(query[i][0] == 1)
            cout << "The count of array elements with value in given range is "
                 << countElementInRange(arr, n, query[i][1], query[i][2], fenwickTree) << endl;
        else if(query[i][0] == 2) {
            cout << "Updating Value \n";
            UpdateValue(arr, n, query[i][1], query[i][2], fenwickTree);
        }
    }
    return 0;
}

Đầu ra

The count of array elements with value in given range is 2
Updating Value
The count of array elements with value in given range is 7