فرض کنید ما ماشینی داریم که می‌تواند مسئله‌ی زیر را در $preprocess،a(n)$ و $Query،b(n)$ حل کند.

یک آرایه‌ی $n$ تایی از اعداد صحیح داده شده است که هر دو عدد مجاور دقیقا در یک واحد اختلاف دارند. در هر $query$ به شما $i$ و $j$ داده می‌شود و شما باید در آرایه کوچک‌ترین عدد بین $i$ امین عنصر و $j$ امین عنصر را به دست آورید. (دقت کنید که این ماشین مکان این کوچک ترین عدد را نیز در آرایه به ما برمی‌گرداند)

حال از شما می‌خواهیم با استفاده از ماشین بالا مسئله‌ی پیدا کردن پایین‌ترین حد مشترک $(LCA)$ در یک درخت ریشه‌دار در زمان $a(2n)$ و $b(2n)$ را حل کنید.

• سوال بعد
• سوال قبل