Square Root Decomposition

problem: একটি N size এর Array তে কিছু নাম্বার দেয়া হল। এখন প্রতিবার x থেকে y রেঞ্জ এর মধ্যে কুয়েরি করে বের করতে হবে minimum নাম্বার কত।
এখন একদম brute force উপায়ে যদি বের করি তাহলে complexity হবে প্রতি query তে x to y iterate করতে হবে. Array size যদি N হয় এবং query যদি N টা হয়। তাহলে worst case complexity হচ্ছে O(N²)। যা খুবই costly.

Square root decomposition:

এখন total Array কে square root size block এ ভাগ করতে হবে।
Array size যদি N হয় তাহলে পুরো Array কে √N size block এ ভাগ করে নিব। এবং প্রতি Block এ √N টা element এর result থাকবে। square root যদি perfect না হয়, তাহলে একদম শেষ Block এ square root থেকে কম element এর রেজাল্ট থাকবে।

এখন যদি 100 size এর একটা Array কে square root decompose করা হয় তাহলে, total block size হবে √100=10 এবং প্রতি Block এ থাকবে 10 টা element এর result.

এখন,
B₀ তে থাকবে index 0 to 9 এর result.
B₁ তে থাকবে index 10 to 19 এর result.
.
.
.
.
.
.
.
B₉ তে থাকবে index 90 to 99 এর result.

Process:

১. Input নেয়ার সময়েই প্রতিটি index এর element এর উত্তর corresponding Block এ calculation করে রেখে দিতে হবে।
২. এখন প্রতি কুয়েরিতে x to y রেঞ্জে যেসব ব্লকে পড়ে তা থেকে result নিয়ে পুরো রেঞ্জের result calculate করতে হবে।
query তে কিছু লক্ষ্যনীয় বিষয়ঃ

• x to y রেঞ্জ এমন হতে পারে যে পুরো x to y কোন একটা ব্লকের sub part. এই ক্ষেত্রে main Array থেকে রেজাল্ট calculate করতে হবে। যেমন 100 size Array এর জন্য 41 to 48
• x to y রেঞ্জ এমন হতে পারে যে range এর left side এর কিছু অংশ একটা Block এ এবং right side এর কিছু অংশ আরেকটা Block এ। এই ক্ষেত্রে আলাদাভাবে দুইটা অংশের result main Array থেকে Calculation করতে হবে। যেমনঃ 100 size Array এর জন্য 45 to 65.

৩. কোন index এর value update এর ক্ষেত্রে ওই index এর corresponding Block এর result update করেতে হবে।
8. কোন index এর corresponding Block = index/blockSize

Complexity:

প্রথমে প্রতি index এর জন্য Block এ রেজাল্ট pre-calculate হচ্ছে O(N) time.
প্রতি query তে maximum সবগুলা Block iterate করা লাগছে। Total Block হচ্ছে √N, সুতরাং worst case এ √N টা block iterate করতে হবে। তাহলে worst case এ সব query complexity হচ্ছে O(N√N)  time.
আর কোন index এর value update করার জন্য, block number বের করা যাচ্ছে, index/blockSize দিয়ে, তাহলে update হচ্ছে O(1) time. কখন যদি এমন হয় ওইব্লকের corresponding সব গুলো

Solution of Above problem:

Code: Square root Decomposition

1. getId ফাংশনের কাজ হল কোন index কত নাম্বার block এ তা বের করে দেয়া।
2. init ফাংশন সবগুলা block কে infinity ভ্যালু নিয়ে initialize করে নিচ্ছে
3. update ফাংশন দিয়ে কোন একটা নির্দিষ্ট index এর ভ্যালু আপডেট করে দেয়া হচ্ছে।
4. query ফাংশন দিয়ে x to y রেঞ্জের result calculation করা হচ্ছে।
   • Line 25 এ যদি রেঞ্জ পুরোটা কোন একটা নির্দিষ্ট block এর sub part হয়ে থাকে, তাহলে main Array থেকে result calculation করে দিবে।
   • Line 32, যদি রেঞ্জ এর lower bound এর কিছু অংশ নির্দিষ্ট একটা block এর sub part হয়ে থাকে তাহলে শুধু সেইটুক sub part এর result main Array থেকে calculate করে দিবে।
   • Line 34, যদি রেঞ্জ এর upper bound এর কিছু অংশ নির্দিষ্ট একটা block এর sub part হয়ে থাকে তাহলে শুধু সেইটুক sub part এর result main Array থেকে নিবে।

এইভাবে Array কে Decompose করে অনেক প্রবলেমের complexity square root এ নিয়ে আসা যায়।

Practice problem: 

1. 1082 – Array Queries
2. 1093 – Ghajini
3. Holes