রেঞ্জ সমষ্টি কোয়েরি 2D - C++ এ অপরিবর্তনীয়

ধরুন আমাদের ম্যাট্রিক্স নামে একটি 2D ম্যাট্রিক্স আছে, আমাদের (সারি 1, কোল1) ব্যবহার করে এবং নীচের ডান কোণে (সারি 1, কোল 1) ব্যবহার করে আয়তক্ষেত্রের ভিতরের উপাদানগুলির যোগফল খুঁজে বের করতে হবে row2, col2)।

তাই ম্যাট্রিক্স যদি −

(2,1) এবং (4,3) দ্বারা সংজ্ঞায়িত নীল রঙ সহ উপরের আয়তক্ষেত্রটিতে যোগফল 8 রয়েছে।

তাই যদি আমরা কিছু কোয়েরি করি যেমন sumRegion(2, 1, 4, 3), sumRegion(1, 1, 2, 2), sumRegion(1, 2, 2, 4), এগুলো যথাক্রমে 8, 11, 12 রিটার্ন করবে।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• dp নামে একটি ম্যাট্রিক্স সংজ্ঞায়িত করুন।

• এইভাবে কাজটি শুরু করুন

• n :=সারির সংখ্যা। যদি n 0 হয়, তাহলে ফেরত দিন,

• m :=কলামের সংখ্যা

• dp :=n x m

  আকারের আরেকটি ম্যাট্রিক্স

• আমি 0 থেকে n

  পরিসরে

  • j এর জন্য 0 থেকে m

    পরিসরে

    • যখন j – 1 <0, তারপর dp[i, j] কে ম্যাট্রিক্স [i, j] হিসাবে সেট করুন, অন্যথায় এটিকে (dp[i, j - 1] + ম্যাট্রিক্স[i, j]) হিসাবে সেট করুন

• আমি 1 থেকে n

  রেঞ্জের মধ্যে

  • j এর জন্য 0 থেকে m

    পরিসরে

    • dp[i – 1, j]

      দ্বারা dp[i, j] বাড়ান

• ক্যোয়ারী পদ্ধতির জন্য, এটি লাগবে row1, col1, row2, col2

• ret :=dp[row2, col2]

• sub1 :=0 যখন সারি 1 – 1 <0, অন্যথায় এটি হবে dp[row1 – 1, col2]

• sub2 :=0 যখন col1 – 1 <0, অন্যথায় এটি হবে dp[row2, col1 - 1]

• যদি সারি 1 – 1 <0 বা col1 – 1 <0, তারপর

  • যোগ করুন :=0

• অন্যথায় যোগ করুন :=dp[row1 – 1, col1 – 1]

• রিটার্ন ret – sub1 – sub2 + add

উদাহরণ(C++)

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

#include নেমস্পেস ব্যবহার করে std;class NumMatrix { সর্বজনীন:vector > dp; NumMatrix(ভেক্টর<ভেক্টর>&ম্যাট্রিক্স) { int n =matrix.size(); যদি(!n) ফিরে আসে; int m =matrix[0].size(); dp =ভেক্টর <ভেক্টর >(n, ভেক্টর  (m)); for(int i =0; i > ম্যাট ={{3,0,1,4,2},{5,6,3,2,1},{1,2,0,1, 5},{4,1,0,1,7},{1,0,3,0,5}}; NumMatrix ob(mat); cout < 
ইনপুট
 <প্রে>[[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7 ],[1,0,3,0,5]]সম অঞ্চল(2,1,4,3)সম অঞ্চল(1,1,2,2)সম অঞ্চল(1,2,2,4)

আউটপুট

81112