এই সমস্যায়, আমাদের একটি অ্যারে অ্যারে [] এবং Q প্রশ্ন দেওয়া হয়েছে, প্রতিটি দুটি প্রকারের একটি হতে পারে,
-
{1, L, R}− রেঞ্জ [L, R]-এ অ্যারের উপাদান গণনার জন্য।
-
{2, index, val}− val এর সাথে সূচীতে উপাদান আপডেট করার জন্য।
আমাদের কাজ হল C++ এ প্রদত্ত পরিসরে মান সহ অ্যারে উপাদানগুলির গণনার জন্য প্রশ্নগুলি সমাধান করার জন্য একটি প্রোগ্রাম তৈরি করা৷
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট :arr[] ={1, 5, 2, 4, 2, 2, 3, 1, 3}
প্রশ্ন =3
প্রশ্ন ={{1, 4, 8},
{2, 6, 5},
{1, 1, 4}}
আউটপুট :3 7
ব্যাখ্যা
প্রশ্ন 1:পরিসরে অ্যারে উপাদান গণনা করুন [4, 8]। গণনা =1
ক্যোয়ারী 2:আপডেট উপাদান arr[6] =5. নতুন অ্যারে, arr[] ={1, 5, 2, 4, 2, 2, 5, 1,3}
প্রশ্ন 1:পরিসরে অ্যারে উপাদান গণনা করুন [4, 8]। গণনা =7
সমাধান পদ্ধতি
সমস্যার একটি সহজ সমাধান হল, সরাসরি অ্যারে ট্র্যাভার্স করে এবং পরিসরে থাকা সমস্ত উপাদানগুলি খুঁজে বের করা, যেমন L =<উপাদান =
প্রতি লুপের জন্য একবার পুনরাবৃত্তি করার সমাধান। তাই এর সময় জটিলতা হল O(Q*N) ক্রম।
সমস্যা সমাধানের একটি ভাল পদ্ধতি বাইনারি ইনডেক্সড ট্রি বা ফেনউইক ট্রি ডেটা স্ট্রাকচার ব্যবহার করা হতে পারে। এখানে, আমরা ট্রিতে অ্যারের উপাদানগুলি সংরক্ষণ করব যা আমাদেরকে অ্যারের উপাদানগুলিকে সূচক হিসাবে ব্যবহার করতে সক্ষম করবে৷ এবং আমরা সহজেই getSumfunction ব্যবহার করে রেঞ্জের উপাদানগুলির গণনা খুঁজে পেতে পারি যা ডেটা কাঠামোর জন্য অন্তর্নির্মিত৷
ElementCount[L, R] =getSum(R) - getSum(L - 1)উদাহরণ
#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
উদাহরণ
#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
