এখানে, আমাদেরকে n আকারের একটি অ্যারে দেওয়া হয়েছে যার প্রাথমিকভাবে সমস্ত উপাদান রয়েছে 0। এবং কিছু প্রশ্ন রয়েছে যা এটিতে সম্পাদন করতে হবে। দুই ধরনের প্রশ্ন আছে −
-
আপডেট(l,r, value) − l থেকে r সূচকের মধ্যে থাকা অ্যারের উপাদানগুলিতে মান যোগ করুন। উদাহরণস্বরূপ, আপডেট(2, 4, 5) সূচক 4 এবং 5 এ উপাদানটিতে 2 উপাদান রেখে অ্যারে আপডেট করবে।
-
getRangeSum(l, r) − l থেকে r পর্যন্ত উপাদানের সীমার মধ্যে উপাদানের সমষ্টি খুঁজুন। উদাহরণস্বরূপ, getRangeSum(4, 7) সূচক 4, 5, 6, 7 সহ সমস্ত উপাদানের যোগফল খুঁজে পাবে।
সমস্যাটি বোঝার জন্য একটি উদাহরণ দেওয়া যাক,
ইনপুট
n =7 , arr[7] ={0,0,0,0,0,0,0}Q1 =আপডেট(3, 6, 4)Q2 =আপডেট(0, 4, 2)Q3 =যোগফল (2, 5) আউটপুট
10
ব্যাখ্যা
প্রশ্নগুলি সমাধান করা:Q1 - আপডেট(3, 6, 4) ={0, 0, 0, 4, 4, 4, 4}Q2 - আপডেট(0, 4, 2) ={2, 2, 2, 2, 2, 4, 4}Q3 - যোগফল(2, 5) =2+2+2+4 =10এই সমস্যাটি সমাধান করার জন্য একটি নিষ্পাপ পন্থা হবে প্রতিটি আপডেট ক্যোয়ারীতে অ্যারে আপডেট করা এবং তারপর যোগফল খুঁজে বের করা কিন্তু এটি এতটা কার্যকর নয় তাই আসুন সমস্যা সমাধানের আরও কার্যকর পদ্ধতি শিখি।
যোগফলের প্রশ্নে আপডেট কোয়েরির প্রভাব দেখা যাক। যোগফলের প্রশ্ন হল যোগফল[l,r] ফর্মের, আমরা এটিকে বিভক্ত করব সমষ্টি [0,k] ফর্মের যোগফলের প্রশ্নে এবং তারপর যোগফলকে যোগফল থেকে নিম্ন সীমাতে বিয়োগ করব।
যোগফল[l,r] =যোগফল[0,r] - যোগফল[0,l]
সুতরাং, যোগফল[0,k] এর প্রভাব যোগফল [l,r] এর উপর প্রতিফলিত হবে। সমষ্টি পরিবর্তনশীল k এর আপেক্ষিক মানের উপর ভিত্তি করে 3টি ভিন্ন অঞ্চলে অবস্থান করবে এবং আপডেট কোয়েরির [l,r] পরিসর হবে।
অঞ্চল 1 − k o এবং l এর মধ্যে অবস্থিত অর্থাৎ 0
এই ক্ষেত্রে, আপডেট কোয়েরি যোগফলের প্রশ্নে প্রভাব ফেলবে না।
অঞ্চল 2 − k l এবং r এর মধ্যে অবস্থিত অর্থাৎ l ≤ k ≤ r
এই ক্ষেত্রে, সমষ্টি প্রশ্নটি l থেকে k পর্যন্ত মানকে মনোরঞ্জন করবে।
অঞ্চল 3 − k r থেকে বড় অর্থাৎ k>r
এই ক্ষেত্রে, সমষ্টি প্রশ্নটি l থেকে r এর মধ্যে সমস্ত মানকে বিনোদন দেবে।
এখন, রেঞ্জ আপডেট এবং রেঞ্জ কোয়েরি
//রেঞ্জ আপডেট এবং রেঞ্জের প্রশ্নগুলি সমাধান করার জন্য প্রোগ্রামউদাহরণ
#include
আউটপুট
সমস্ত আপডেট প্রশ্ন প্রয়োগ করার পরে যোগফলের আউটপুট হল
