Truy vấn số phần tử khác nhau trong mảng con | Phần 2 trong C++

Trong bài toán này, ta được cho mảng arr[] kích thước n và một truy vấn. Mỗi truy vấn chứa hai giá trị (L, R). Nhiệm vụ là tạo chương trình giải quyết truy vấn: số phần tử khác nhau trong mảng con.

Mô tả bài toán

Cần tìm tổng số nguyên khác nhau xuất hiện trong mảng con từ chỉ số (L-1) đến (R-1).

Ví dụ minh họa

Đầu vào

arr[] = {4, 6, 1, 3, 1, 6, 5}
query = [1, 4]

Đầu ra

4

Giải thích

Truy vấn 1: L = 1, R = 4, tìm số phần tử khác nhau từ chỉ số 0 đến 3, kết quả là 4.

Truy vấn 2: L = 2, R = 6, tìm số phần tử khác nhau từ chỉ số 1 đến 5, kết quả là 3.

Phương pháp giải

Cách đơn giản: duyệt mảng từ L đến R, thêm vào set, kích thước set là kết quả (đã thảo luận ở phần trước).

Cách hiệu quả hơn: sử dụng cấu trúc dữ liệu Segment Tree (cây đoạn). Segment tree lưu trữ số phần tử khác nhau cho từng đoạn.

Segment Tree là cây đặc biệt lưu thông tin theo đoạn. Nút lá đại diện cho phần tử mảng. Nút không lá đại diện cho đoạn với giá trị cần thiết (ở đây là tập các phần tử khác nhau). Triển khai dùng set.

Chương trình triển khai:

Ví dụ

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

set<int>* segmentTree;

void CreateSegmentTree(int i, int s, int e, int arr[]) {
    if (s == e) {
        segmentTree[i].insert(arr[s]);
        return;
    }
    CreateSegmentTree(2 * i, s, (s + e) / 2, arr);
    CreateSegmentTree(1 + 2 * i, 1 + (s + e) / 2, e, arr);
    segmentTree[i].insert(segmentTree[2 * i].begin(), segmentTree[2 * i].end());
    segmentTree[i].insert(segmentTree[2 * i + 1].begin(), segmentTree[2 * i + 1].end());
}

set<int> findDistSubarray(int node, int l, int r, int a, int b) {
    set<int> left, right, distinctSubarray;
    if (b < l || a > r)
        return distinctSubarray;
    if (a <= l && r <= b)
        return segmentTree[node];
    left = findDistSubarray(2 * node, l, (l + r) / 2, a, b);
    distinctSubarray.insert(left.begin(), left.end());
    right = findDistSubarray(1 + 2 * node, 1 + (l + r) / 2, r, a, b);
    return distinctSubarray;
}

int main() {
    int arr[] = {4, 6, 1, 3, 1, 6, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int query[] = {1, 4};
    int i = (int)ceil(log2(n));
    i = (2 * (pow(2, i))) - 1;
    segmentTree = new set<int>[i];
    CreateSegmentTree(1, 0, n - 1, arr);
    set<int> distCount = findDistSubarray(1, 0, n - 1, (query[0]-1), (query[1]-1));
    cout << "The number of distinct elements in the subarray is " << distCount.size();
    return 0;
}

Đầu ra

The number of distinct elements in the subarray is 4