راه خطی برای LCA¶

در بخش قبل دیدیم که چگونه می توان مسائل LCA و RMQ را به هم تبدیل کرد. اگر توجه کنید وقتی که LCA را به RMQ تبدیل می کنیم، آرایه ای ساخته می شود که اختلاف اعضایش دقیقا یک واحد است. این مساله خاص را در زمان خطی حل می کنیم که از آن نتیجه می شود که LCA و RMQ نیز در زمان \(O(n+q)\) حل می شوند. توجه کنید که این راه ارزش تئوری دارد و با توجه به پیچیدگی پیاده سازی و ضریب بالا، در عمل استفاده نمی شود.

در این راه آرایه را به دسته های \(\frac{lg(n)}{2}\) تایی تقسیم می کنیم. چون اختلاف هر دو عضو متوالی دقیقا ۱ است، این آرایه از لحاظ ساختار در کل \(2^{\frac{lg(n)}{2}} = \sqrt{n}\) حالت ممکن می تواند داشته باشد. برای هر کدام از زیر بازه های این حالات عضو مینیمم را به دست می آوریم که با پیاده سازی خوب پیچیدگی زمانی و حافظه ای \(O(\sqrt{n} * lg^2(n))\) خواهد داشت. برای هر بازه نیز به دست بیاورید که شبیه کدام یک از رادیکال حالت ممکن است. این کار نیز در زمان خطی قابل اجراست. سپس هر دسته را یک عضو از یک آرایه جدید بگیرید و روی آن یک جدول پراکنده مشابه آن چه در بخش قبل بررسی کردیم بسازید. این کار نیز در زمان \(O(\frac{2*n}{lg(n)}*lg(\frac{2*n}{lg(n)})) = O(n)\) قابل اجراست.

حال می خواهیم به پرسش ها پاسخ دهیم. یک بازه را در نظر بگیرید. یا کاملا درون یکی از دسته های کوچک می افتد که جواب آن را از قبل حساب کرده ایم. و یا سر آن درون یک بازه و ته آن درون بازه ای دیگر است. دسته های وسط که کامل درون بازه افتاده اند را به کمک جدول پراکنده ای که حساب کردیم عضو کمینه اش را حساب کنید. دو بازه سر و ته را نیز مانند حالت اول عمل کنید. سپس عضو کمینه بین این سه کاندید را حساب کنید. این عضو جواب شماست.