समस्या विवरण
इस समस्या में, हमें एक सरणी arr[] और Q क्वेरीज़ दी गई हैं, जिनमें से प्रत्येक दो प्रकार की हो सकती हैं,
- {1, L, R} - रेंज [L, R] में सरणी तत्वों की संख्या के लिए।
- {2, index, val} - इंडेक्स पर तत्व को 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
व्याख्या
क्वेरी 1: रेंज [4, 8] में सरणी तत्वों की गणना। गणना = 1
क्वेरी 2: तत्व arr[6] = 5 अपडेट करें। नई सरणी, arr[] = {1, 5, 2, 4, 2, 2, 5, 1, 3}
क्वेरी 1: रेंज [4, 8] में सरणी तत्वों की गणना। गणना = 7
समाधान दृष्टिकोण
समस्या का एक सरल समाधान, सीधे सरणी को पार करके और उन सभी तत्वों को ढूंढकर है जो रेंज में हैं यानी L <= तत्व <= R।
कार्यक्रम उदाहरण (सरल दृष्टिकोण)
#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 << "दी गई रेंज में मान वाले सरणी तत्वों की संख्या " << countElementInRange(arr,N, query[i][1], query[i][2]) << endl;
else if(query[i][0] == 2){
cout << "मान अपडेट हो रहा है \n";
arr[query[i][1]] = query[i][2];
}
}
return 0;
}
आउटपुट
दी गई रेंज में मान वाले सरणी तत्वों की संख्या 2 मान अपडेट हो रहा है दी गई रेंज में मान वाले सरणी तत्वों की संख्या 7
इस दृष्टिकोण का समाधान प्रत्येक लूप के लिए एक बार पुनरावृति करता है। इसलिए इसकी समय जटिलता O(Q*N) क्रम की है।
समस्या को हल करने का एक बेहतर दृष्टिकोण बाइनरी इंडेक्स्ड ट्री या फेनविक ट्री (Fenwick Tree) डेटा संरचना का उपयोग करना हो सकता है। यहां, हम सरणी के तत्वों को ट्री में संग्रहीत करेंगे जो हमें सरणी तत्वों को इंडेक्स के रूप में उपयोग करने में सक्षम करेगा। और हम आसानी से गेटसम (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 << "दी गई रेंज में मान वाले सरणी तत्वों की संख्या " << countElementInRange(arr, n, query[i][1], query[i][2], fenwickTree) << endl;
else if(query[i][0] == 2){
cout << "मान अपडेट हो रहा है \n";
UpdateValue(arr, n, query[i][1], query[i][2], fenwickTree);
}
}
return 0;
}
आउटपुट
दी गई रेंज में मान वाले सरणी तत्वों की संख्या 2 मान अपडेट हो रहा है दी गई रेंज में मान वाले सरणी तत्वों की संख्या 7
