এই সমস্যায়, আমাদেরকে n আকারের একটি অ্যারে অ্যারে দেওয়া হয়েছে এবং আমাদের অ্যাক্যুয়েরি দেওয়া হয়েছে। প্রতিটি ক্যোয়ারীতে দুটি মান রয়েছে (L, R)। আমাদের কাজ হল একটি সাবঅ্যারেতে স্বতন্ত্র উপাদানের সংখ্যার জন্য প্রশ্নের সমাধান করার জন্য একটি প্রোগ্রাম তৈরি করা
সমস্যা বর্ণনা − এখানে, আমাদেরকে সূচক (L-1) থেকে (R-1) পর্যন্ত সাব্যারেতে উপস্থিত স্বতন্ত্র পূর্ণসংখ্যার মোট সংখ্যা খুঁজে বের করতে হবে।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
arr[] = {4, 6, 1, 3, 1, 6, 5}
query = [1, 4] আউটপুট
4
ব্যাখ্যা
ক্যোয়ারী 1:L =1 এবং R =4 এর জন্য, আমাদের সূচক 0 থেকে 3 পর্যন্ত পার্থক্যের সংখ্যা খুঁজে বের করতে হবে, যা 4।
প্রশ্ন 2:L =2 এবং R =6 এর জন্য, আমাদের সূচক 1 থেকে 5 পর্যন্ত স্বতন্ত্র উপাদানের সংখ্যা খুঁজে বের করতে হবে, যা 3।
সমাধান পদ্ধতি
প্রতিটি প্রশ্নের সমাধান করার জন্য একটি সহজ পদ্ধতি হল এল থেকে রেন্ড স্টোরের উপাদানগুলিকে সেটে নিয়ে যাওয়া, যার আকার কোয়েরির ফলাফল দেবে৷ আমরা শেষ সেটে একই আলোচনা করেছি৷
সমস্যা সমাধানের আরও কার্যকর উপায় হল সেগমেন্ট ট্রি ডেটাস্ট্রাকচার ব্যবহার করা। এটি প্রদত্ত পরিসরের জন্য স্বতন্ত্র উপাদান গণনা সংরক্ষণ করবে।
একটি সেগমেন্ট ট্রি এটি একটি বিশেষ ধরনের গাছ, যা তথ্য সেগমেন্ট আকারে সংরক্ষণ করে।
সেগমেন্ট গাছের পাতার নোড অ্যারের উপাদানগুলিকে নির্দেশ করে। এবং নন-লিফ নোডগুলি প্রয়োজনীয় মান সহ সেগমেন্টগুলিকে নির্দেশ করে। এখানে, এটি স্বতন্ত্র উপাদান সংরক্ষণ করবে। এই ডেটা স্ট্রাকচার বাস্তবায়নের জন্য, আমরা সেট ব্যবহার করব।
উপরের সমাধানের কাজ বাস্তবায়নের জন্য প্রোগ্রাম -
উদাহরণ
#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;
} আউটপুট
The number of distinct elements in the subarray is 4
