एक एरे और कई क्वेरी दी गई हैं। साथ ही, दो प्रकार की क्वेरी हैं, यानी, अपडेट[L, R] का मतलब L से R तक के तत्वों को उनके वर्गमूल से अपडेट करना, और क्वेरी[L, R] का मतलब L से R तक के तत्वों का योग निकालना है। हम 1-आधारित इंडेक्स्ड एरे मान रहे हैं, उदाहरण के लिए:
इनपुट: nums[] = {0, 9, 4, 1, 5, 2, 3}, Query[] = {{1, 1, 3}, {2, 1, 2}, {1, 2, 5}, {1, 4, 5}}
आउटपुट: 14 10 7
पहली क्वेरी का पहला तत्व 1 है मतलब हमें 1 से 3 तक रेंज सम निकालना है यानी 9 + 4 + 1 = 14
दूसरी क्वेरी का पहला तत्व 2 है मतलब हमें 1 से 2 तक रेंज तत्व को उनके वर्गमूल से अपडेट करना है अब नया arr[] एरे है {3, 2, 1, 5, 2, 3}
तीसरी क्वेरी का पहला तत्व 1 है मतलब हमें 2 से 5 तक रेंज सम निकालना है यानी 2 + 1 + 5 + 2 = 10
चौथी क्वेरी का पहला तत्व 1 है मतलब हमें 4 से 5 तक रेंज सम निकालना है यानी 5 + 2 = 7
इनपुट: nums[] = {0, 3, 2, 4, 16, 2}, Query[] = {{1, 1, 3}, {2, 2, 5}}
आउटपुट: 9
समाधान खोजने का दृष्टिकोण
सरल दृष्टिकोण
हम क्वेरी समाप्त होने तक एक लूप का उपयोग कर सकते हैं और सम क्वेरी के लिए रेंज का योग रिटर्न कर सकते हैं और अपडेट क्वेरी के लिए एरे को अपडेट कर सकते हैं। लेकिन इस प्रोग्राम की समय जटिलता O(q * n) होगी। आइए एक कुशल दृष्टिकोण देखें।
कुशल दृष्टिकोण
प्रोग्राम कुशल हो सकता है यदि हम ऑपरेशन की संख्या या पुनरावृत्तियों की संख्या कम करते हैं। हम बाइनरी इंडेक्स्ड ट्रीज़ का उपयोग कर सकते हैं, जिसमें हम एक एरे बनाते हैं और अपडेट और सम क्वेरी के लिए दो फंक्शन का उपयोग करते हैं। अपडेट क्वेरी के लिए, यदि तत्व 1 है, तो इसे अपडेट करने की कोई आवश्यकता नहीं है क्योंकि इसका वर्गमूल केवल एक ही होगा। अब हम एक सेट का उपयोग करके 1 से अधिक तत्वों के इंडेक्स को स्टोर कर सकते हैं और Lवें इंडेक्स को खोजने के लिए बाइनरी सर्च का उपयोग कर सकते हैं और इसे तब तक बढ़ा सकते हैं जब तक हर रेंज तत्व अपडेट न हो जाए। फिर जांचें कि क्या अपडेट किया गया मान 1 बन जाता है, तो उस इंडेक्स को सेट से हटा दें क्योंकि यह किसी भी अपडेट क्वेरी के लिए हमेशा 1 रहेगा।
सम क्वेरी के लिए, हम query(R) - query(L-1) कर सकते हैं।
उदाहरण
उपरोक्त दृष्टिकोण के लिए C++ कोड
#include <bits/stdc++.h>
using namespace std;
// इनपुट एरे का अधिकतम आकार
const int m = 200;
// बाइनरी इंडेक्स्ड ट्री बनाना।
int binary_indexed[m + 1];
// अपडेट क्वेरी के लिए
void update_q(int a, int x, int n) {
while (a <= n) {
binary_indexed[a] += x;
a += a & -a;
}
}
// रेंज सम निकालने का फंक्शन।
int sum_q(int a) {
int s = 0;
while (a > 0) {
s += binary_indexed[a];
a -= a & -a;
}
return s;
}
int main() {
int no_query = 4;
int nums[] = {0, 9, 4, 1, 5, 2, 3};
int n = sizeof(nums) / sizeof(nums[0]);
// क्वेरी के लिए 2-D एरे।
int q[no_query + 1][3];
q[0][0] = 1, q[0][1] = 1, q[0][2] = 3;
q[1][0] = 2, q[1][1] = 1, q[1][2] = 2;
q[2][0] = 1, q[2][1] = 2, q[2][2] = 5;
q[3][0] = 1, q[3][1] = 4, q[3][2] = 5;
set s;
for (int i = 1; i < n; i++) {
// 1 से अधिक तत्वों के इंडेक्स को सेट में डालना।
if (nums[i] > 1)
s.insert(i);
update_q(i, nums[i], n);
}
for (int i = 0; i < no_query; i++) {
// 0वें इंडेक्स की जांच अपडेट क्वेरी या सम क्वेरी के लिए।
if (q[i][0] == 2) {
while (true) {
// बाइनरी सर्च का उपयोग करके बायां इंडेक्स ढूंढना
auto it = s.lower_bound(q[i][1]);
// जांचना कि क्या यह दाएं इंडेक्स तक पहुंचता है।
if (it == s.end() || *it > q[i][2])
break;
q[i][1] = *it;
// एरे तत्व को उनके वर्गमूल से अपडेट करना।
update_q(*it, (int)sqrt(nums[*it]) - nums[*it], n);
nums[*it] = (int)sqrt(nums[*it]);
// जांचना कि क्या अपडेट किया गया मान 1 है तो इसे सेट से हटाना
if (nums[*it] == 1)
s.erase(*it);
q[i][1]++;
}
} else {
cout << "क्वेरी" << i+1 << ": " << (sum_q(q[i][2]) - sum_q(q[i][1] - 1)) << endl;
}
}
return 0;
}
आउटपुट
क्वेरी1: 14 क्वेरी3: 10 क्वेरी4: 7
निष्कर्ष
इस ट्यूटोरियल में, हमने एरे के लिए रेंज सम क्वेरी और रेंज अपडेट क्वेरी पर चर्चा की। हमने इस समस्या को हल करने के लिए एक सरल दृष्टिकोण और बाइनरी इंडेक्स्ड ट्री का उपयोग करके एक कुशल दृष्टिकोण पर चर्चा की। हमने इस समस्या के लिए C++ प्रोग्राम पर भी चर्चा की जिसे हम C, Java, Python आदि प्रोग्रामिंग भाषाओं के साथ कर सकते हैं। आशा है कि आपको यह ट्यूटोरियल मददगार लगा होगा।
