ตรวจสอบตัวเลขในช่วงที่กำหนดด้วย Segment Tree ใน C++

ภาพรวมปัญหา

ได้รับอาร์เรย์และ Q คำถาม แต่ละคำถามมีช่วง [L, R] และค่า val ตรวจสอบว่า val มีอยู่ในช่วงนั้นหรือไม่

ตัวอย่าง

arr[] = {4, 8, 1, 7, 2, 9, 3, 5, 1}
Query 1: [1, 4, 3] -> subarray {8,1,7,2} -> 3 not present
Query 2: [0, 2, 1] -> subarray {4,8,1} -> 1 present
Query 3: [4, 7, 2] -> subarray {2,9,3,5,1} -> 2 present

วิธีแก้ปัญหา

วิธีตรวจสอบตรง - O(N) ต่อคำถาม

วนลูปตรวจสอบในช่วง [L, R]

วิธี Segment Tree + Set - O(log N) ต่อคำถาม

• แต่ละโหนดเก็บ Set ของตัวเลขที่ปรากฏในช่วงนั้น (สูงสุด 10 ตัวคือ 0-9)
• Merge: Union ของ set ลูก
• Query: ตรวจสอบ val ใน set ของโหนดที่ครอบคลุมช่วง

ตัวอย่างโค้ด C++ (Segment Tree)

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

set SegTree[36];

void buildSegmentTree(int* arr, int index, int start, int end) {
    if (start == end) {
        SegTree[index].insert(arr[start]);
        return;
    }
    int mid = (start + end) >> 1;
    buildSegmentTree(arr, 2*index, start, mid);
    buildSegmentTree(arr, 2*index+1, mid+1, end);
    for (auto it : SegTree[2*index]) SegTree[index].insert(it);
    for (auto it : SegTree[2*index+1]) SegTree[index].insert(it);
}

bool isElementPresent(int index, int start, int end, int L, int R, int val) {
    if (L <= start && end <= R)
        return SegTree[index].count(val) > 0;
    if (R < start || end < L) return false;
    int mid = (start + end) >> 1;
    return isElementPresent(2*index, start, mid, L, R, val) ||
           isElementPresent(2*index+1, mid+1, end, L, R, val);
}

int main() {
    // ... build tree and process queries
    return 0;
}