স্কয়ার রুট ডিকম্পোজিশন একটা টেকনিক যা কিছু বেসিক প্রবলেমকে (সাব-অ্যারে
সাম বের করা, একটি সাব-অ্যারেতে মিনিমাম/মাক্সিমাম এলিমেন্ট বের করা,
ইত্যাদি) \( O(\sqrt{N}) \) অপারেশনে বের করতে সাহায্য করে। ধরি, \(N\)
এলিমেন্টের জন্য আমরা সাব-অ্যারে সাম বের করবো। প্রথমত আমরা অ্যারেটাকে
\(\sqrt{N}\)-ব্লকে ভাগ করে ফেলি (এক্ষেত্রে প্রতিটা ব্লকের সাইজও হবে
\(\sqrt{N}\)) তারপর প্রতিটা ব্লকের জন্য সাম বের করি। এখন যদি \((l, r)\)
রেঞ্জের জন্য সাব-অ্যারে সাম বের করতে বলা হয় তবে আমরা সর্বপ্রথম দেখবো যে
\(l\) এবং \(r\) কোন ব্লকে পরে। \(l\) এবং \(r\) যে ব্লকে পরবে ওই ব্লকগুলো
বাদ দিয়ে এদের মধ্যবর্তি সকল ব্লকের সাম \(\sqrt{N}\)-এ বের করা সম্ভব। \(l\)
থেকে \(l\) যে ব্লকের অন্তর্গত তার শেষ পর্যন্ত সাম এবং \(r\) যে ব্লকের
অন্তর্গত তার শুরু থেকে \(r\) পর্যন্ত সাম \(\sqrt{N}\)-এ বের করা সম্ভব।
সুতরাং, \(O(\sqrt{N})\) কমপ্লেক্সিটিতে আমরা \((l, r)\) রেঞ্জের জন্য
সাব-অ্যারে সাম বের করতে পারছি। (কাজটা কিভাবে হচ্ছে এটা নিজে নিজে বুঝার
চেষ্টা করি, চেষ্টা করার পরও বের করতে না পারলে কমেন্ট সেকশনে জানালে আমি
উদাহরণ দিয়ে বুঝিয়ে দেওয়ার চেষ্টা করবো।)
উপরোক্ত টেকনিকটি আমরা MO’s অ্যালগোরিদমে ব্যবহার করতে পারি। এই অ্যালগরিদমটি
দিয়ে আমরা রেঞ্জ কুয়েরির প্রবলেম গুলো সলভ করতে পারি। যদি \(Q\) টি কুয়েরি
থাকে এবং অ্যারের সাইজ \(N\) হয় তবে অ্যালগোরিদমের কমপ্লেক্সিটি হবে
\(O((N+Q)\sqrt{N})\).
অ্যালগরিদমটিকে একটি প্রবলেম এর মাধ্যমে ব্যাখ্যা করতে পারলে সবথেকে ভালো
হয়। তাই আমি এখানে একটি সহজ প্রবলেম এর মাধ্যমে এই অ্যালগরিদমটি ব্যাখ্যা
করার চেষ্টা করলাম।
প্রোব্লেম: একটা \(N\) সাইজের অ্যারে দেওয়া আছে এবং \(Q\) টি কুয়েরি
দেওয়া আছে। প্রতি কুয়েরিতে \((l,r)\) রেঞ্জ এর প্রতি এলিমেন্টের সাম বের করতে
হবে। ধরি, \(N = 14\) এবং \(Q = 6\), কুয়েরি গুলো হচ্ছে (1 indexed) - \[\{(2, 7), (3,
4), (3, 10), (6, 12), (11, 12), (10, 12)\}\]
এর জন্য two pointer দিয়ে সলিউশন এর কপ্লেক্সিটি হবে \(O(N^2)\)
কিন্তু কুয়েরি গুলোকে একটি নির্দিষ্ট উপায়ে সর্ট করলে একই সলিউশনের
কপ্লেক্সিটি \(O(N\sqrt{N})\) এ নামিয়ে আনা সম্ভব। (Magic!! তাই না?)\(...\)
আচ্ছা এখন তাহলে এই ম্যাজিক এর পেছনের রহস্যটা দেখা যাক।
প্রথমত আমরা দেখব কিভাবে কুয়েরি গুলো নির্দিষ্ট উপায়ে সর্ট করা যায়।
সর্বপ্রথম আমরা অ্যারেটিকে \(\sqrt{N}\) ব্লকে ভাগ করবো, যেখানে প্রতিটি
ব্লকের সাইজও হবে \(\sqrt{N}\)। প্রতি কুয়েরিতে দুইটা পার্ট আছে, \(l\) এবং
\(r\), এগুলোকে আমরা যথাক্রমে স্টার্টিং পয়েন্ট এবং এন্ডিং পয়েন্ট হিসেবে
চিহ্নিত করব। এখন এই স্টার্টিং পয়েন্ট এবং এন্ডিং পয়েন্টগুলো অবশ্যই কোন না
কোন ব্লকের মধ্যে পড়বে। একটি কুয়েরি \(ith\) ব্লকের অন্তর্গত হবে যদি সেই
কুয়েরির স্টার্টিং পয়েন্ট \(ith\) ব্লকে পরে। এই অ্যালগরিদমে আমরা ১ম ব্লকের
কুয়েরি গুলোকে নিয়ে সর্বপ্রথম কাজ করব এরপরে আমরা ২য় ব্লকের কুয়েরি
গুলোকে নিয়ে কাজ করব এবং এভাবে সর্বশেষে \(\sqrt{N}th\) ব্লক নিয়ে কাজ করব।
তাই সর্টিং এর সময় কুয়েরিগুলোকে ব্লকের আরোহী ক্রমে সাজাবো।
এক্ষেত্রে একই ব্লকে একাধিক কুয়েরি থাকতে পারে। এখন একই ব্লকের সকল কুয়েরি
কে একটি গ্রুপ হিসেবে চিন্তা করব এবং প্রতি গ্রুপের কুয়েরিগুলোকে তাদের \(r\)
এর ভ্যালুর উপর নির্ভর করে আরোহী ক্রমে সর্ট করবো। সর্বশেষ কুয়েরির
অর্ডারটা দেখতে এমন হবে -
চিত্রে, প্রতি ঘরের ভিতরে অ্যারের ইনডেক্স নাম্বার লিখা আছে। অ্যারেটিকে
\(\left\lceil{\sqrt{14}}\right\rceil \approx 4 \) টি ব্লকে ভাগ করা হয়েছে
(রেড লাইন দিয়ে ব্লকগুলো আলাদা করা হয়েছে)। প্রতি ব্লকের সাইজও \(4\) (শেষ ব্লকের সাইজ কম হতে পারে)। প্রতি
কুয়েরিকে বিভিন্ন রঙের সরলরেখা দিয়ে প্রকাশ করা হয়েছে। প্রথমে কুয়েরি গুলোকে
ব্লক নাম্বারের উপর নির্ভর করে সর্ট করা হয়েছে। তারপর প্রতি ব্লকের কুয়েরি
গুলোকে তাদের \(r\) এর ভ্যালুর উপর নির্ভর করে সর্ট করা হয়েছে (ইহা কুয়েরি
গুলোর ডানপাশের নাম্বার দিয়ে বুঝানো হল)। সর্টিং এর পর কুয়েরিগুলোর অর্ডার
হবে - \[\{(3, 4), (2, 7), (3, 10), (6, 12), (10, 12), (11, 12)\}\] এখন এই
কুয়েরিগুলো নিয়ে two pointer সলিউশন লিখা সম্ভব যা
\(O((N+Q)\sqrt{N})\) তে কাজ করবে। এখন প্রশ্ন হচ্ছে এটা কেন এই
কমপ্লেক্সিটিতে কাজ করবে?!
ধরি, আমাদের কাছে দুইটি পয়েন্টার আছে, লেফট পয়েন্টার এবং রাইট পয়েন্টার। প্রতি ব্লকের জন্য রাইট
পয়েন্টার সর্বদা ইনক্রিজিং অর্ডারে মুভ করবে। সুতরাং, প্রতিটি ব্লকের জন্য
এই পয়েন্টারটি সর্বোচ্চ \(N\) বার মুভ করতে পারবে। এজন্য এর কমপ্লেক্সিটি হবে
\(O(N\sqrt{N})\)। লেফট পয়েন্টারের মুভ নির্ভর করবে কুয়েরি নাম্বারের উপর,
প্রতি কুয়েরির জন্য এটা সর্বোচ্চ \(\sqrt{N}\) টি মুভ করতে পারে (ব্লকের সাইজের সমান)। তাই এর
কমপ্লেক্সিটি হবে \(O(Q\sqrt{N})\)। এজন্য অ্যালগরিদমটির কমপ্লেক্সিটি হবে
\(O((N+Q)\sqrt{N})\)।
কিছু উপলব্ধিঃ
- কুয়েরিগুলো অফলাইন আন্সার করা হয়, অনলাইন কুয়েরির জন্য এই অ্যালগরিদম কাজ করবে না।
- ব্লক সাইজ রানটাইমে কম্পিউট না করে const হিসেবে ব্যবহার করা ভাল।
- বিজোড় ব্লকে রাইট ইন্ডেক্সকে আরোহী ক্রমে এবং জোড় ব্লকে এটিকে অবরোহ ক্রমে সাজালে এটি রাইট পয়েন্টারের মুভমেন্ট কমিয়ে দেয়, কারণ স্বাভাবিক অর্ডারে প্রতিটি ব্লকের শুরুতে রাইট পয়েন্টারটিকে শেষ থেকে শুরুতে ফিরিয়ে নিয়ে যাবে।
- add() এবং del() এর মধ্যে add() এর কাজ আগে করে নেওয়া ভাল, নয়তো অনেক সময় এমন ভ্যালু delete করতে হতে পারে যা এখনো অ্যাড করা হয় নাই। (code দেখলে এদের কাজ বুঝা যাবে)
- সেগমেন্ট ট্রী দিয়ে কিছু প্রব্লেম সল্ভ করা অনেক কঠিন হতে পারে (এমনকি নাও সল্ভ করা যেতে পারে) যা এই অ্যালগরিদম দিয়ে খুব সহজে সল্ভ করা সম্ভব।
কিছু প্রব্লেমঃ
No comments:
Post a Comment