LCA দিয়ে Range Minimum Query (RMQ) সমাধান#

একটি অ্যারে A[0..N-1] দেওয়া আছে। প্রতিটি [L, R] আকারের কুয়েরির জন্য আমরা A অ্যারেতে L অবস্থান থেকে শুরু করে R অবস্থানে শেষ হওয়া রেঞ্জে মিনিমাম বের করতে চাই। আমরা ধরে নিচ্ছি যে A অ্যারে প্রক্রিয়ার মধ্যে পরিবর্তন হয় না, অর্থাৎ এই আর্টিকেলটা স্ট্যাটিক RMQ সমস্যার সমাধান বর্ণনা করে।

এখানে একটি অ্যাসিম্পটটিক্যালি অপটিমাল সমাধানের বর্ণনা দেওয়া হলো। এটি RMQ সমস্যার অন্যান্য সমাধান থেকে আলাদা, কারণ এটি তাদের থেকে খুবই ভিন্ন: এটি RMQ সমস্যাকে LCA সমস্যায় রিডিউস করে, এবং তারপর ফারাক-কোল্টন ও বেন্ডার অ্যালগরিদম ব্যবহার করে, যেটি LCA সমস্যাকে আবার একটি বিশেষায়িত RMQ সমস্যায় রিডিউস করে এবং সেটি সমাধান করে।

অ্যালগরিদম#

আমরা A অ্যারে থেকে একটি কার্তেসিয়ান ট্রি তৈরি করি। A অ্যারের কার্তেসিয়ান ট্রি হলো মিন-হিপ বৈশিষ্ট্যযুক্ত (প্যারেন্ট নোডের মান তার চিলড্রেনের মানের চেয়ে ছোট বা সমান হতে হবে) একটি বাইনারি ট্রি, যেখানে ট্রি-র ইন-অর্ডার ট্রাভার্সাল A অ্যারের নোডগুলোকে একই ক্রমে ভিজিট করে।

অন্যভাবে বলতে গেলে, কার্তেসিয়ান ট্রি হলো একটি রিকার্সিভ ডেটা স্ট্রাকচার। A অ্যারেকে ৩ ভাগে ভাগ করা হবে: মিনিমাম পর্যন্ত অ্যারের প্রিফিক্স, মিনিমাম, এবং অবশিষ্ট সাফিক্স। ট্রি-র রুট হবে A অ্যারের মিনিমাম উপাদানের সাথে সংশ্লিষ্ট নোড, বাম সাবট্রি হবে প্রিফিক্সের কার্তেসিয়ান ট্রি, এবং ডান সাবট্রি হবে সাফিক্সের কার্তেসিয়ান ট্রি।

নিচের ছবিতে তুমি ১০ দৈর্ঘ্যের একটি অ্যারে এবং তার সংশ্লিষ্ট কার্তেসিয়ান ট্রি দেখতে পারবে।

RMQ [l, r] হলো LCA কুয়েরি [l', r']-এর সমতুল্য, যেখানে l' হলো A[l] উপাদানের সাথে সংশ্লিষ্ট নোড এবং r' হলো A[r] উপাদানের সাথে সংশ্লিষ্ট নোড। আসলে, রেঞ্জে সবচেয়ে ছোট উপাদানের সাথে সংশ্লিষ্ট নোডটি অবশ্যই রেঞ্জের সব নোডের অ্যানসেস্টর হবে, তাই l' এবং r'-এরও। এটি মিন-হিপ বৈশিষ্ট্য থেকে স্বয়ংক্রিয়ভাবে আসে। এবং এটিকে সবচেয়ে নিচের অ্যানসেস্টরও হতে হবে, কারণ অন্যথায় l' এবং r' উভয়ই বাম বা ডান সাবট্রিতে থাকত, যা একটি বিরোধ তৈরি করে কারণ সেক্ষেত্রে মিনিমাম রেঞ্জে থাকতই না।

নিচের ছবিতে তুমি RMQ কুয়েরি [1, 3] এবং [5, 9]-এর জন্য LCA কুয়েরি দেখতে পারবেন। প্রথম কুয়েরিতে A[1] এবং A[3] নোডের LCA হলো A[2]-এর সাথে সংশ্লিষ্ট নোড যার মান ২, এবং দ্বিতীয় কুয়েরিতে A[5] এবং A[9]-এর LCA হলো A[8]-এর সাথে সংশ্লিষ্ট নোড যার মান ৩।

এরকম ট্রি $O(N)$ সময়ে তৈরি করা যায় এবং ফারাক-কোল্টন ও বেন্ডারের অ্যালগরিদম $O(N)$-এ ট্রি প্রিপ্রসেস করে $O(1)$-এ LCA বের করতে পারে।

কার্তেসিয়ান ট্রি নির্মাণ#

আমরা উপাদানগুলো একটির পর একটি যোগ করে কার্তেসিয়ান ট্রি তৈরি করব। প্রতিটি ধাপে আমরা ইতোমধ্যে প্রসেস করা সব উপাদানের একটি ভ্যালিড কার্তেসিয়ান ট্রি বজায় রাখি। সহজেই দেখা যায় যে, s[i] উপাদান যোগ করলে শুধু ট্রি-র সবচেয়ে ডান পাথের (রুট থেকে শুরু করে বারবার ডান চাইল্ড নিয়ে) নোডগুলো পরিবর্তিত হতে পারে। সবচেয়ে ছোট কিন্তু s[i]-এর চেয়ে বড় বা সমান মানের নোডের সাবট্রি s[i]-এর বাম সাবট্রি হয়ে যাবে, এবং s[i] রুটযুক্ত ট্রি সবচেয়ে বড় কিন্তু s[i]-এর চেয়ে ছোট মানের নোডের নতুন ডান সাবট্রি হবে।

এটি একটি স্ট্যাক ব্যবহার করে ইমপ্লিমেন্ট করা যায় যেটি সবচেয়ে ডান নোডগুলোর ইনডেক্স সংরক্ষণ করে।

vector<int> parent(n, -1);
stack<int> s;
for (int i = 0; i < n; i++) {
    int last = -1;
    while (!s.empty() && A[s.top()] >= A[i]) {
        last = s.top();
        s.pop();
    }
    if (!s.empty())
        parent[i] = s.top();
    if (last >= 0)
        parent[last] = i;
    s.push(i);
}