इस समस्या में, हमें एक सरणी गिरफ्तारी [] और क्यू प्रश्न दिए गए हैं, प्रत्येक दो प्रकारों में से एक हो सकता है,
-
{1, एल, आर}− श्रेणी [एल, आर] में सरणी तत्वों की गणना के लिए।
-
{2, इंडेक्स, वैल}− इंडेक्स पर एलिमेंट को वैल के साथ अपडेट करने के लिए।
हमारा कार्य 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:अद्यतन तत्व गिरफ्तारी [6] =5। नई सरणी, गिरफ्तारी [] ={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