একটি অ্যারে এবং বিভিন্ন প্রশ্ন দেওয়া. এছাড়াও, দুটি ধরণের কোয়েরি রয়েছে, যেমন, আপডেট[ L, R ] মানে L থেকে R থেকে তাদের বর্গমূলের উপাদানগুলিকে আপডেট করা, এবং ক্যোয়ারী[ L, R ] মানে L থেকে R থেকে উপাদানগুলির যোগফল গণনা করা। আমরা একটি 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 সমাধান খোঁজার পদ্ধতি
সরল পদ্ধতি
আমরা ক্যোয়ারী শেষ না হওয়া পর্যন্ত একটি লুপ ব্যবহার করতে পারি এবং যোগফল কোয়েরির জন্য পরিসরের যোগফল ফেরত দিতে পারি এবং আপডেট কোয়েরির জন্য অ্যারে আপডেট করতে পারি। কিন্তু এই প্রোগ্রামের সময় জটিলতা হবে O(q * n)। আসুন একটি দক্ষ পদ্ধতির সন্ধান করি।
দক্ষ পদ্ধতি
প্রোগ্রামটি কার্যকর হতে পারে যদি আমরা অপারেশনের সংখ্যা বা পুনরাবৃত্তির সংখ্যা হ্রাস করি। আমরা Binary Indexed Trees ব্যবহার করতে পারি, যেখানে আমরা একটি অ্যারে তৈরি করি এবং আপডেট এবং যোগফলের জন্য দুটি ফাংশন ব্যবহার করি। আপডেট কোয়েরির জন্য, যদি উপাদানটি 1 হয়, তবে এটিকে আপডেট করার দরকার নেই কারণ এর বর্গমূল শুধুমাত্র একটি হবে। এখন আমরা একের বেশি সূচক সংরক্ষণ করতে একটি সেট ব্যবহার করতে পারি এবং Lth সূচক খোঁজার জন্য বাইনারি অনুসন্ধান ব্যবহার করতে পারি এবং প্রতিটি রেঞ্জ উপাদান আপডেট না হওয়া পর্যন্ত এটি বৃদ্ধি করতে পারি। তারপরে আপডেট করা মানটি এক হয়ে যায় কিনা তা পরীক্ষা করে দেখুন, তারপর সেট থেকে সেই সূচকটি সরিয়ে ফেলুন কারণ এটি যেকোনো আপডেটের প্রশ্নের জন্য সর্বদা 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++ প্রোগ্রাম নিয়েও আলোচনা করেছি যা আমরা সি, জাভা, পাইথন ইত্যাদি প্রোগ্রামিং ভাষার সাথে করতে পারি। আমরা আশা করি এই টিউটোরিয়ালটি আপনার কাজে লাগবে।
