এই সমস্যাতে, আমাদের একটি অ্যারে arr[] এবং Q সংখ্যক কোয়েরি দেওয়া আছে, যেগুলো নিচের দুটি টাইপের হতে পারে,
{1, L, R} − মানের রেঞ্জ [L, R]-এ অ্যারে এলিমেন্টের কাউন্ট।
{2, index, val} − index-এ অবস্থিত এলিমেন্টকে val দিয়ে আপডেট করা।
আমাদের কাজ হলো C++-এ দেয়া রেঞ্জে অ্যারে এলিমেন্টের কাউন্ট কোয়েরি সমাধান করার প্রোগ্রাম লিখা।
উদাহরণ দিয়ে বুঝি,
ইনপুট:arr[] = {1, 5, 2, 4, 2, 2, 3, 1, 3}
Q = 3
Query = { {1, 4, 8},
{2, 6, 5},
{1, 1, 4}}
আউটপুট:3 7
ব্যাখ্যা
কোয়েরি ১: মানের রেঞ্জ [4, 8]-এ অ্যারে এলিমেন্টের কাউন্ট = ১
কোয়েরি ২: arr[6] = 5 দিয়ে আপডেট। নতুন অ্যারে, arr[] = {1, 5, 2, 4, 2, 2, 5, 1, 3}
কোয়েরি ১: মানের রেঞ্জ [4, 8]-এ অ্যারে এলিমেন্টের কাউন্ট = ৭
সমাধান পদ্ধতি
সমস্যার একটি সহজ সমাধান হচ্ছে সরাসরি অ্যারে ট্রাভার্স করে রেঞ্জে থাকা সব এলিমেন্ট বের করা।
উদাহরণ
#include <iostream>
using namespace std;
int countElementInRange(int arr[], int N, int L, int R){
int ValueCount = 0;
for (int i = 0; i < N; i++) {
if (arr[i] >= L && arr[i] <= R) {
ValueCount++;
}
}
return ValueCount;
}
int main() {
int arr[] = {1, 5, 2, 4, 2, 2, 3, 1, 3};
int N = sizeof(arr) / sizeof(arr[0]);
int Q = 3;
int query[Q][3] = { {1, 4, 8},{2, 6, 5},{1, 1, 4}};
for(int i = 0; i < Q; i++){
if(query[i][0] == 1)
cout<<"The count of array elements with value in given range is " <<countElementInRange(arr,N, query[i][1], query[i][2])<<endl;
else if(query[i][0] == 2){
cout<<"Updating Value \n";
arr[query[i][1]] = query[i][2];
}
}
return 0;
}আউটপুট
The count of array elements with value in given range is 2 Updating Value The count of array elements with value in given range is 7
এই পদ্ধতির টাইম কমপ্লেক্সিটি O(Q*N)।
একটি আরও ভালো পদ্ধতি হচ্ছে বাইনারি ইন্ডেক্সড ট্রি বা ফেনউইক ট্রি ডেটা স্ট্রাকচার ব্যবহার করা। এখানে অ্যারে এলিমেন্টগুলো ট্রিতে সংরক্ষণ করা হবে যা এলিমেন্টকে ইনডেক্স হিসেবে ব্যবহার করতে দেবে। এবং getSum ফাংশন ব্যবহার করে রেঞ্জের এলিমেন্ট কাউন্ট সহজে বের করা যাবে।
ElementCount[L, R] = getSum(R) - getSum(L - 1)
উদাহরণ
#include <iostream>
using namespace std;
class BinaryIndTree {
public:
int* BIT;
int N;
BinaryIndTree(int N) {
this->N = N;
BIT = new int[N];
for (int i = 0; i < N; i++) {
BIT[i] = 0;
}
}
void update(int index, int increment) {
while (index < N) {
BIT[index] += increment;
index += (index & -index);
}
}
int calcSum(int index) {
int sum = 0;
while (index > 0) {
sum += BIT[index];
index -= (index & -index);
}
return sum;
}
};
void UpdateValue(int* arr, int n, int index, int val, BinaryIndTree*fenwickTree){
int removedElement = arr[index];
fenwickTree->update(removedElement, -1);
arr[index] = val;
fenwickTree->update(val, 1);
}
int countElementInRange(int* arr, int n, int L, int R, BinaryIndTree* fenwickTree) {
return fenwickTree->calcSum(R) - fenwickTree->calcSum(L - 1);
}
int main() {
int arr[] = { 1, 5, 2, 4, 2, 2, 3, 1, 3 };
int n = sizeof(arr) / sizeof(arr[0]);
int Q = 3;
int query[Q][3] = { {1, 4, 8},{2, 6, 5},{1, 1, 4}};
int N = 100001;
BinaryIndTree* fenwickTree = new BinaryIndTree(N);
for (int i = 0; i < n; i++)
fenwickTree->update(arr[i], 1);
for(int i = 0; i < Q; i++){
if(query[i][0] == 1)
cout<<"The count of array elements with value in given range is "<<countElementInRange(arr, n, query[i][1], query[i][2],fenwickTree)<<endl;
else if(query[i][0] == 2){
cout<<"Updating Value \n";
UpdateValue(arr, n, query[i][1], query[i][2], fenwickTree);
}
}
return 0;
}আউটপুট
The count of array elements with value in given range is 2 Updating Value The count of array elements with value in given range is 7
