অ্যালগরিদম - Algorithmsডাটা স্ট্রাকচার - Data structures

ডাটা স্ট্রাকচার: স্কয়ার রুট ডিকম্পোজিশন

Square root decomposition/Square root segmentation Bengali tutorial

স্কয়ার রুট ডিকম্পোজিশন (Square root decomposition aka: Square root segmentation) হলো একটি ডাটা স্ট্রাকচার (Data structure) যার মাধ্যমে আমরা কিছু কমন অপারেশন (কুয়েরি, আপডেট) ইত্যাদি O(\sqrt(n)) এ করতে পারি। যা O(n) এর থেকে বেশ দ্রুত। ধরা যাক আমাদেরকে n সাইজের একটি অ্যারে a[n] দেয়া আছে। আমাদেরকে q টি কুয়েরি করা হবে এবং প্রতি কুয়েরিতে হয় আমাদেরকে যেকোনো রেঞ্জ l-r এর যোগফল বলা লাগবে অথবা আমাদেরকে a[] এর যেকোনো ইনডেক্স i কে আপডেট করতে হবে।

আমরা উপরের সমস্যাটিকে সেগমেন্ট ট্রি/ বাইনারি ইন্ডেক্সড ট্রি দিয়েও সমাধান করতে পারি। তবে আজকে আমরা স্কয়ার রুট ডিকম্পোজিশন ব্যবহার করে সমস্যাটির সমাধান করবো O(\sqrt(n)) কমপ্লেক্সিটি তে।

স্কয়ার রুট ডিকম্পোজিশন (Square root decomposition) এর বেসিক আইডিয়া হলো অ্যারেকে আমাদের প্রি-প্রসেস বা পূর্ব-প্রক্রিয়াকরণ করে নিতে হবে। আমরা আমাদের অ্যারে a[] কে এমনভাবে আলদা করে ব্লক করবো যাতে করি প্রতি ব্লকে x=\lfloor \sqrt(n) \rfloor পরিমাণ ইলিমেন্ট থাকে। শেষের ব্লকে একটু কম হতে পারে। আমরা তা সহজেই হেন্ডেল করতে পারবো। সুতরাং আমাদের ব্লক সংখ্যা যদি s হয় তবে s=\lceil \frac{n}{x} \rceil

আমরা s সাইজের একটি অ্যারে b[s] নিলাম যার মাঝে আমরা আমাদের মূল অ্যারেকে ব্লক করার পর তার ইলিমেন্ট গুলোর মান যোগ করে রাখবো।

\underbrace{a[0]+a[1]+…+a[x−1]}_{b[0]},\underbrace{a[x]+a[x+1]+…+a[2x−1]}_{b[1]},\underbrace{a[2x]+a[2x+1]+…+a[3x−1]}_{b[2]}

এভাবে আমরা b[] অ্যারেতে আমাদের মূল অ্যারে a[] কে বিভক্ত করে রাখবো। এভাবেই আমরা আমাদের স্কয়ার রুট সেগমেন্ট তৈরি করবো। নিচের কোডটি দেখি,

উপরের কোডে a[] অ্যারের জন্য তৈরি প্রতিটি ব্লকের লিমেন্ট গুলোর যোগফল b[] অ্যারেতে রাখা হবে। এর সাইজ আমরা s=\lceil \frac{n}{x} \rceil দিয়ে হিসাব না করে সরাসরি ১০০ দিয়ে দিয়েছি। আপনারা চাইলে হিসাব করেও জায়গা নিতে পারেন। ৭ নং লাইনে আমরা প্রতিটি ব্লকের সাইজ হিসাব করেছি x=\lfloor \sqrt(n) \rfloor এই সূত্র দিয়ে। তারপরের লুপে আমরা পুরো অ্যারে ট্রাভার্স করেছি এবং if(i%segment_size==0) দিয়ে দেখেছি কোথায় কোথায় আমাদের নতুন সেগমেন্ট শুরু করতে হবে। সেখানে সেখানে আমরা সেগমেন্ট ইনডেক্স k এর মান বাড়িয়েছি। তারপর ১৩ নং লাইনে আমরা উপযুক্ত সেগমেন্টে মানগুলো যোগ করেছি।

স্কয়ার রুট ডিকম্পোজিশন: কুয়েরি করা-Square root decomposition: Query

আমরা খুব সহজেই যেকোনো রেঞ্জ l-r এর মধ্যে কুয়েরি করতে পারি O(\sqrt(n)) কমপ্লেক্সিটিতে। নিচের ছবিটা দেখি। আমাদেরকে একটি অ্যারে a[] দেয়া আছে। আমাদেরকে l=1 থেকে r=10 পর্যন্ত ইলিমেন্ট গুলোর যোগফল খুঁজে বের করতে হবে O(\sqrt(n)) এ।

Square root decomposition example

এখানে আমাদের ব্লক সাইজ হলো \lfloor \sqrt(13) \rfloor = 3 , যা শুরুতেই বিভিন্ন রঙ দিয়ে চিহ্নিত করা। দেখা যাচ্ছে l=1 থেকে r=10 এর সবুজ এবং সোনালি রঙের ব্লক দুইটি পুরোপুরি আমাদের রেঞ্জের মধ্যে পরেছে। অপরদিকে আকাশী এবং লাল ব্লক আংশিক পরেছে। আংশিক ওভারলেপ (Overlap) / উপরিপাতনের জন্য আমরা ওই সেগমেন্টগুলোর প্রতিটি ইনডেক্স ঘুরে যোগফল নিবো। অন্যদিকে সম্পূর্ণ ওভারলেপ/ উপরিপাতনের জন্য আমরা শুধু সেগমেন্টগুলোর প্রি-ক্যালকুলেটেড মান গুলো নিবো।

কুয়েরি ফাংশনের ৩ টি ধাপ হবে। প্রথম ধাপে আমরা সর্ব বামের আংশিক ওভারলেপ যে ব্লকটি আছে তার যোগফল বের করবো। দ্বিতীয় ধাপে আমরা সম্পূর্ণ ওভারলেপ অংশগুলোর যোগফল নিবো। এবং তৃতীয় ধাপে আমরা সর্ব বামের আংশিক ওভারলেপ জায়গাটুকুর যোগফল বের করবো। আমরা কোডটি দেখি।

এখানে লক্ষণীয় যে আংশিক ওভারলেপ শুধু প্রথম এবং শেষের ব্লক গুলোতেই সম্ভব। তাই আমরা প্রথমে সাধারণভাবে sum ভেরিয়েবলে a[l] এর মান রেখেছি এবং l এর মান এক-এক করে বাড়িয়েছি। এখানে l%segment_size!=0 নিশ্চিত করবে আমরা কুয়েরির শুরুর ব্লকেই রয়েছি।

কুয়েরির প্রথম অংশ শেষ হলে মাঝের অংশের ব্লক গুলোতে ঢুকবে। যেহেতু এরা সম্পূর্ণ ওভারলেপ করেছে তাই আমাদের এদের যোগফল a[] এর প্রতিটি ইলিমেন্ট ঘুরে বের করতে হবে না। আমরা শুধু এক ব্লক থেকে আরেক ব্লকে জাম্প করবো। এখানে আমরা দেখতে পাচ্ছি b[] অ্যারেতে আমরা আগে যে প্রি-ক্যালকুলেট করে যোগফল রেখেছিলাম তাকে আমরা \lfloor \frac{l}{\text{segment_size}} \rfloor দিয়ে বের করেছি। বুঝতে সমস্যা হলে অ্যারেতে এই অপারেশন টা ভিজুয়ালাইজ করে দেখুন।

তৃতীয় অংশে আমরা আরেকটি লুপ ব্যবহার করেছি এবং এর মধ্যে আমরা প্রথমবারের মতো সাধারণ উপায়ে যোগফল বের করেছি।

এখন আসা যাক কেনও কুয়েরি অপারেশন O(\sqrt(n)) এ করা যাবে। আমরা দেখলাম কুয়েরি রেঞ্জের প্রথম এবং শেষ সেগমেন্টের আংশিক ওভারলেপ হতে পারে। এই ক্ষেত্রে আমাদের ব্লকের অন্তর্ভুক্ত প্রতিটি ইনডেক্সে লুপ ঘুরিয়ে এক এক করে যোগফল বের করে আনতে হবে। আমাদের সর্বোচ্চ \lfloor \sqrt(n) \rfloor +1 টি ব্লক থাকতে পারে এবং প্রতি ব্লকে সর্বোচ্চ \lfloor \sqrt(n) \rfloor টি উপদান থাকতে পারে। সুতরাং যদিও আমাদের প্রথম এবং শেষ সেগমেন্টে লুপ ঘুরাতে হয়েছিলো তবুও আমাদের কমপ্লেক্সিটি O(\sqrt(n)) থাকবে।

স্কয়ার রুট ডিকম্পোজিশন: আপডেট করা-Square root decomposition: Update

এখানে আপডেট করা খুবই সহজ। আমরা O(1) এই একটি ইনডেক্স i কে আপডেট করতে পারি। এর জন্য আমাদের যা করতে হবে তা হলো i কোন সেগমেন্টে আছে তাকে খুঁজে বের করতে হবে \lfloor \frac{l}{\text{segment_size}} \rfloor এই সূত্র দিয়ে। তারপর ওই সেগমেন্ট থেকে a[i] বাদ দিতে হবে, এবং নতুন মান val যোগ করতে হবে। নিচের কোডটি দেখি,

এভাবে খুব দ্রুত আমরা স্কয়ার রুট ডিকম্পোজিশন ব্যবহার করে রেঞ্জ আপডেট করতে পারি এবং রেঞ্জ কুয়েরি করতে পারি। যদিও এই পদ্ধতি সেগমেন্ট ট্রি এর মতো দ্রুত না তবুও এটার বিভিন্ন আপ্লিকেশন তো আছেই।

স্কয়ার রুট ডিকম্পোজিশন: সম্পূর্ণ কোড

প্রাকটিস প্রবলেম

আরও জানতে এই ব্লগ টি পরতে পারেন https://codeforces.com/blog/entry/20489

Leave a Reply

Your email address will not be published. Required fields are marked *

Back to top button