Trong bài toán này, chúng ta được cung cấp một mảng arr [] có kích thước n và chúng ta được cung cấp cho bể nước. Mỗi truy vấn chứa hai giá trị (L, R). nhiệm vụ của chúng ta là tạo một chương trình để giải quyết các truy vấn cho một số phần tử riêng biệt trong một mảng con
Mô tả sự cố - Ở đây, chúng ta sẽ cần tìm tổng số các số nguyên riêng biệt có trong mảng con từ chỉ mục (L-1) đến (R-1).
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
arr[] = {4, 6, 1, 3, 1, 6, 5}
query = [1, 4] Đầu ra
4
Giải thích
Đối với truy vấn 1:L =1 &R =4, chúng ta cần tìm số lượng các phần tử phân biệt từ chỉ mục 0 đến 3, là 4.
Đối với truy vấn 2:L =2 &R =6, chúng ta cần tìm số phần tử riêng biệt từ chỉ số 1 đến 5, là 3.
Phương pháp tiếp cận giải pháp
Một cách tiếp cận đơn giản để giải quyết từng truy vấn là duyệt qua mảng từ L đến Rand các phần tử lưu trữ vào tập hợp, kích thước của chúng sẽ cho kết quả của querry.
Một cách hiệu quả hơn để giải quyết vấn đề là sử dụng cấu trúc dữ liệu cây phân đoạn. Nó sẽ lưu trữ số phần tử riêng biệt cho phạm vi đã cho.
Cây phân đoạn là một loại cây đặc biệt, lưu trữ thông tin dưới dạng các phân đoạn.
Nút lá của cây phân đoạn biểu thị các phần tử của mảng. Và các nút không phải lá biểu thị các đoạn có giá trị bắt buộc. Ở đây, nó sẽ lưu trữ các yếu tố riêng biệt. Để triển khai cấu trúc dữ liệu này, chúng tôi sẽ sử dụng Set.
Chương trình triển khai hoạt động của giải pháp trên -
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