Truy vấn kiểm tra chữ số có tồn tại trong đoạn [L, R] C++

Cho mảng arr[] và Q truy vấn. Mỗi truy vấn: L, R, val. Kiểm tra val có xuất hiện trong arr[L..R] không.

Ví dụ

arr = {4, 8, 1, 7, 2, 9, 3, 5, 1}
Q1: L=1, R=4, val=3 → {8,1,7,2} → NO
Q2: L=0, R=2, val=1 → {4,8,1} → YES
Q3: L=4, R=7, val=2 → {2,9,3,5} → YES

Phương pháp 1: Duyệt trực tiếp O(N) mỗi truy vấn

Đơn giản, phù hợp N, Q nhỏ.

Phương pháp 2: Cây đoạn (Segment Tree) với Set

Mỗi nút cây đoạn lưu set các giá trị khác nhau trong đoạn đó. Vì giá trị là chữ số (0-9) hoặc nhỏ, set rất nhỏ (≤10).

• Xây dựng: gộp set của 2 con (union).
• Truy vấn: kiểm tra val có trong set của đoạn không.
• Cập nhật: thay đổi giá trị lá, cập nhật lên cha.

Độ phức tạp: O(log N) mỗi truy vấn/cập nhật.

Chương trình C++

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

const int MAXN = 100005;
vector> seg(4 * MAXN); // Dùng unordered_set cho O(1) trung bình

void build(int node, int l, int r, const vector& arr) {
    if (l == r) {
        seg[node].insert(arr[l]);
        return;
    }
    int mid = (l + r) / 2;
    build(node*2, l, mid, arr);
    build(node*2+1, mid+1, r, arr);
    seg[node] = seg[node*2];
    seg[node].insert(seg[node*2+1].begin(), seg[node*2+1].end());
}

bool query(int node, int l, int r, int ql, int qr, int val) {
    if (qr < l || r < ql) return false;
    if (ql <= l && r <= qr) return seg[node].count(val);
    int mid = (l + r) / 2;
    return query(node*2, l, mid, ql, qr, val) || 
           query(node*2+1, mid+1, r, ql, qr, val);
}

void update(int node, int l, int r, int idx, int oldVal, int newVal) {
    seg[node].erase(oldVal);
    seg[node].insert(newVal);
    if (l == r) return;
    int mid = (l + r) / 2;
    if (idx <= mid) update(node*2, l, mid, idx, oldVal, newVal);
    else update(node*2+1, mid+1, r, idx, oldVal, newVal);
}

int main() {
    vector arr = {4, 8, 1, 7, 2, 9, 3, 5, 1};
    int n = arr.size();
    build(1, 0, n-1, arr);
    
    cout << "Query [1,4] val=3: " << (query(1,0,n-1,1,4,3) ? "YES" : "NO") << endl;
    cout << "Query [0,2] val=1: " << (query(1,0,n-1,0,2,1) ? "YES" : "NO") << endl;
    cout << "Query [4,7] val=2: " << (query(1,0,n-1,4,7,2) ? "YES" : "NO") << endl;
    return 0;
}

Kết quả

Query [1,4] val=3: NO
Query [0,2] val=1: YES
Query [4,7] val=2: YES

Tối ưu thêm

Nếu giá trị ≤ 10⁵, có thể dùng bitset hoặc mảng bool thay set để nhanh hơn.