রেঞ্জ মিনিমাম কুয়েরি (আরএমকিউ)#
আপনাকে একটি অ্যারে $A[1..N]$ দেওয়া আছে। আপনাকে $(L, R)$ আকারের আগত কুয়েরিগুলোর উত্তর দিতে হবে, যেগুলো অ্যারে $A$-তে $L$ এবং $R$ অবস্থানের মধ্যে (সহ) ন্যূনতম উপাদান খুঁজতে বলে।
আরএমকিউ সরাসরি সমস্যায় আসতে পারে অথবা অন্য কোনো কাজে প্রয়োগ করা যেতে পারে, যেমন লোয়েস্ট কমন অ্যানসেস্টর সমস্যা।
সমাধান#
আরএমকিউ কাজ সমাধানের জন্য অনেক সম্ভাব্য পদ্ধতি এবং ডেটা স্ট্রাকচার আছে।
এই সাইটে যেগুলো ব্যাখ্যা করা হয়েছে সেগুলো নিচে তালিকাভুক্ত করা হলো।
প্রথমে সেই পদ্ধতিগুলো যেগুলো কুয়েরির উত্তর দেওয়ার মাঝে অ্যারেতে পরিবর্তনের অনুমতি দেয়।
- Sqrt-ডিকম্পোজিশন - প্রতিটি কুয়েরির উত্তর $O(\sqrt{N})$-এ, প্রিপ্রসেসিং $O(N)$-এ। সুবিধা: খুব সহজ ডেটা স্ট্রাকচার। অসুবিধা: দুর্বল কমপ্লেক্সিটি।
- সেগমেন্ট ট্রি - প্রতিটি কুয়েরির উত্তর $O(\log N)$-এ, প্রিপ্রসেসিং $O(N)$-এ। সুবিধা: ভালো টাইম কমপ্লেক্সিটি। অসুবিধা: অন্যান্য ডেটা স্ট্রাকচারের তুলনায় বেশি কোড।
- ফেনউইক ট্রি - প্রতিটি কুয়েরির উত্তর $O(\log N)$-এ, প্রিপ্রসেসিং $O(N \log N)$-এ। সুবিধা: সবচেয়ে সংক্ষিপ্ত কোড, ভালো টাইম কমপ্লেক্সিটি। অসুবিধা: ফেনউইক ট্রি শুধুমাত্র $L = 1$ যুক্ত কুয়েরির জন্য ব্যবহার করা যায়, তাই এটি অনেক সমস্যায় প্রযোজ্য নয়।
এবং এখানে সেই পদ্ধতিগুলো যেগুলো শুধুমাত্র স্ট্যাটিক অ্যারেতে কাজ করে, অর্থাৎ সম্পূর্ণ ডেটা স্ট্রাকচার পুনর্গণনা না করে অ্যারের কোনো মান পরিবর্তন করা সম্ভব নয়।
- স্পার্স টেবিল - প্রতিটি কুয়েরির উত্তর $O(1)$-এ, প্রিপ্রসেসিং $O(N \log N)$-এ। সুবিধা: সহজ ডেটা স্ট্রাকচার, চমৎকার টাইম কমপ্লেক্সিটি।
- Sqrt ট্রি - কুয়েরির উত্তর $O(1)$-এ, প্রিপ্রসেসিং $O(N \log \log N)$-এ। সুবিধা: দ্রুত। অসুবিধা: ইমপ্লিমেন্ট করা জটিল।
- ডিসজয়েন্ট সেট ইউনিয়ন / আরপার ট্রিক - কুয়েরির উত্তর $O(1)$-এ, প্রিপ্রসেসিং $O(n)$-এ। সুবিধা: সংক্ষিপ্ত, দ্রুত। অসুবিধা: শুধুমাত্র তখনই কাজ করে যখন সব কুয়েরি আগে থেকে জানা থাকে, অর্থাৎ শুধুমাত্র অফ-লাইন প্রসেসিং সাপোর্ট করে।
- কার্তেসিয়ান ট্রি এবং ফারাচ-কোল্টন ও বেন্ডার অ্যালগরিদম - কুয়েরির উত্তর $O(1)$-এ, প্রিপ্রসেসিং $O(n)$-এ। সুবিধা: অপটিমাল কমপ্লেক্সিটি। অসুবিধা: অনেক বেশি কোড।
দ্রষ্টব্য: প্রিপ্রসেসিং হলো দেওয়া অ্যারের প্রাথমিক প্রক্রিয়াকরণ, এর জন্য সংশ্লিষ্ট ডেটা স্ট্রাকচার তৈরি করা।