एक सरणी और कई प्रश्नों को देखते हुए। इसके अलावा, दो प्रकार की क्वेरी हैं, अर्थात्, अद्यतन [एल, आर] का अर्थ है एल से आर तक तत्वों को उनके वर्गमूल के साथ अद्यतन करना, और क्वेरी [एल, आर] का अर्थ है एल से आर तक तत्वों के योग की गणना करना। हम हैं उदाहरण के लिए, 1-आधारित अनुक्रमित सरणी मानते हुए
Input: nums[ ] = { 0, 9, 4, 1, 5, 2, 3 }, Query[ ] = { {1, 1, 3}, {2, 1, 2}, {1, 2, 5}, { 1, 4, 5}}
Output: 14
10
7
1st element of 1st query is 1 means we need to calculate range sum from 1 to 3 i.e 9 + 4 + 1 = 14
1st element of 2nd query is 2 means we need to update range element from 1 to 2 with their square roots now new arr[] array is { 3, 2, 1, 5, 2, 3 }
1st element of 3rd query is 1 means we need to calculate range sum from 2 to 5 i.e 2 + 1 + 5 + 2 = 10
1st element of the 4th query is 1 means we need to calculate the range sum from 4 to 5 i.e 5 + 2 = 7
Input: nums[] = { 0, 3, 2, 4, 16, 2 }, Query[ ] = {{1, 1, 3}, {2, 2, 5}}
Output: 9 समाधान खोजने के लिए दृष्टिकोण
सरल तरीका
हम क्वेरी समाप्त होने तक लूप का उपयोग कर सकते हैं और सम क्वेरी के लिए श्रेणी का योग वापस कर सकते हैं और अद्यतन क्वेरी के लिए सरणी को अपडेट कर सकते हैं। लेकिन इस कार्यक्रम की समय जटिलता ओ (क्यू * एन) होगी। आइए एक कुशल दृष्टिकोण की तलाश करें।
कुशल दृष्टिकोण
यदि हम संचालन की संख्या या पुनरावृत्तियों की संख्या घटाते हैं तो कार्यक्रम कुशल हो सकता है। हम बाइनरी इंडेक्स ट्री का उपयोग कर सकते हैं, जिसमें हम एक सरणी बनाते हैं और अद्यतन और योग क्वेरी के लिए दो कार्यों का उपयोग करते हैं। अद्यतन क्वेरी के लिए, यदि तत्व 1 है, तो इसे अद्यतन करने की कोई आवश्यकता नहीं है क्योंकि इसका वर्गमूल केवल एक ही होगा। अब हम एक से अधिक के इंडेक्स को स्टोर करने के लिए एक सेट का उपयोग कर सकते हैं और एलटीएच इंडेक्स खोजने के लिए बाइनरी सर्च का उपयोग कर सकते हैं और इसे तब तक बढ़ा सकते हैं जब तक कि हर रेंज एलिमेंट अपडेट न हो जाए। फिर जांचें कि क्या अपडेट किया गया मान एक हो जाता है, फिर उस इंडेक्स को सेट से हटा दें क्योंकि यह किसी भी अपडेट क्वेरी के लिए हमेशा 1 रहेगा।
सम क्वेरी के लिए, हम query(R) - query(L-1) कर सकते हैं।
उदाहरण
उपरोक्त दृष्टिकोण के लिए C++ कोड
#include <bits/stdc++.h>
using namespace std;
// Maximum size input array can be
const int m = 200;
// Creating Binary Indexed tree.
int binary_indexed[m + 1];
// for update query
void update_q(int a, int x, int n){
while(a <= n) {
binary_indexed[a] += x;
a += a & -a;
}
}
// Function to calculate sum range.
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 array for queries.
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<int> s;
for (int i = 1; i < n; i++) {
// Inserting indexes in the set of elements that are greater than 1.
if (nums[i] > 1)
s.insert(i);
update_q(i, nums[i], n);
}
for (int i = 0; i < no_query; i++) {
// Checking 0th index for update query or sum query.
if (q[i][0] == 2) {
while (true) {
// Finding the left index using binary search
auto it = s.lower_bound(q[i][1]);
// checking whether it reaches right index.
if (it == s.end() || *it > q[i][2])
break;
q[i][1] = *it;
// updating array element to their square roots.
update_q(*it, (int)sqrt(nums[*it]) - nums[*it], n);
nums[*it] = (int)sqrt(nums[*it]);
//checking if updated value is 1 the removing it from set
if (nums[*it] == 1)
s.erase(*it);
q[i][1]++;
}
} else {
cout <<"query" << i+1 <<": " << (sum_q(q[i][2]) - sum_q(q[i][1] - 1)) << endl;
}
}
return 0;
} आउटपुट
query1: 14 query3: 10 query4: 7
निष्कर्ष
इस ट्यूटोरियल में, हमने एरे के लिए रेंज सम क्वेरी और रेंज अपडेट क्वेरी पर चर्चा की। हमने इस समस्या को हल करने के लिए एक सरल दृष्टिकोण और बाइनरी इंडेक्स ट्री का उपयोग करके एक कुशल दृष्टिकोण पर चर्चा की। हमने इस समस्या के लिए C++ प्रोग्राम पर भी चर्चा की जिसे हम प्रोग्रामिंग भाषाओं जैसे C, Java, Python, आदि के साथ कर सकते हैं। हमें उम्मीद है कि आपको यह ट्यूटोरियल मददगार लगेगा।