Đếm số lượng phần tử nhỏ nhất trong đoạn [L,R] của mảng C++

Cho mảng N phần tử và đoạn [L, R] (chỉ số 1-based). Đếm số lần xuất hiện của giá trị nhỏ nhất trong đoạn này.

Ví dụ minh họa

Ví dụ 1:

• Input: arr = {1, 2, 3, 0, 3, 2, 0, 1}, N=8, L=2, R=5
• Output: 1
• Giải thích: Đoạn arr[1..4] = {2, 3, 0, 3}. Min = 0, xuất hiện 1 lần.

Ví dụ 2:

• Input: arr = {1, 2, 3, 0, 3, 2, 0, 1}, N=8, L=3, R=8
• Output: 2
• Giải thích: Đoạn arr[2..7] = {3, 0, 3, 2, 0, 1}. Min = 0, xuất hiện 2 lần.

Mã nguồn C++ (Đơn giản O(N) mỗi truy vấn)

#include <bits/stdc++.h>
using namespace std;

int countSmallest(int arr[], int n, int l, int r) {
    // Chuyển sang 0-based index
    l--; r--;
    if (l < 0 || r >= n) return 0;
    
    int smallest = arr[l];
    for (int i = l; i <= r; i++) {
        if (arr[i] < smallest) smallest = arr[i];
    }
    
    int count = 0;
    for (int i = l; i <= r; i++) {
        if (arr[i] == smallest) count++;
    }
    return count;
}

int main() {
    int arr[] = {3, 2, 1, 1, 2, 3};
    int n = 6;
    int L = 1, R = 5;
    cout << "So phan tu nho nhat trong [" << L << "," << R << "]: " 
         << countSmallest(arr, n, L, R) << endl;
    L = 3, R = 4;
    cout << "So phan tu nho nhat trong [" << L << "," << R << "]: " 
         << countSmallest(arr, n, L, R);
    return 0;
}

Kết quả chạy chương trình

So phan tu nho nhat trong [1,5]: 2
So phan tu nho nhat trong [3,4]: 2

Tối ưu cho nhiều truy vấn - Segment Tree / Sparse Table

Nếu có Q truy vấn, O(N) mỗi truy vấn quá chậm. Dùng cấu trúc dữ liệu:

Sparse Table (RMQ) - O(1) query, O(N log N) build

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
const int LOG = 18;
int st[MAXN][LOG];
int freq[MAXN][LOG]; // Tần suất của min trong đoạn

void buildSparseTable(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        st[i][0] = arr[i];
        freq[i][0] = 1;
    }
    for (int j = 1; (1 << j) <= n; j++) {
        for (int i = 0; i + (1 << j) <= n; i++) {
            int left = st[i][j-1];
            int right = st[i + (1 << (j-1))][j-1];
            if (left < right) {
                st[i][j] = left;
                freq[i][j] = freq[i][j-1];
            } else if (left > right) {
                st[i][j] = right;
                freq[i][j] = freq[i + (1 << (j-1))][j-1];
            } else {
                st[i][j] = left;
                freq[i][j] = freq[i][j-1] + freq[i + (1 << (j-1))][j-1];
            }
        }
    }
}

pair query(int l, int r) { // 0-based, inclusive
    int len = r - l + 1;
    int k = 31 - __builtin_clz(len);
    int leftMin = st[l][k];
    int rightMin = st[r - (1 << k) + 1][k];
    if (leftMin < rightMin) return {leftMin, freq[l][k]};
    if (leftMin > rightMin) return {rightMin, freq[r - (1 << k) + 1][k]};
    return {leftMin, freq[l][k] + freq[r - (1 << k) + 1][k]};
}

Segment Tree - O(log N) query, O(N) build

Lưu trữ (min_value, count) tại mỗi node. Gộp 2 node con theo quy tắc so sánh min.

Độ phức tạp