ارتباط LCA و RMQ¶
در ادامه به بررسی یک مساله دیگر می‌پردازیم که در ظاهر به موضوع بحث نامربوط است اما ارتباط نزدیکی به مساله LCA دارد. سپس به کمک حل این مساله یک راه حل از اردر \(O(n*lg(n)+q)\) ارائه می‌کنیم که در صورت زیاد بودن تعداد پرسش ها نسبت به رئوس درخت، از راه قبل بهتر عمل می‌کند.
در این مساله ابتدا یک آرایه n راسی به شما داده می‌شود و سپس از شما q پرسش انجام می‌شود که در هر پرسش، دو سر یک بازه به شما داده می‌شود و از شما کمینه اعضای این بازه خواسته می‌شود. شما به کمک درخت بازه‌ای که در قبل خواندید می‌توانید این مساله را از \(O(n+q*lg(n))\) حل کنید. اگر به جای کمینه اعضا، جمع اعضا خواسته می‌شد نیز می‌توانستید به راحتی و از \(O(n+q)\) مساله را حل کنید. به این مساله RMQ می‌گویند که مخفف پرسش کمینه در بازه است.
تبدیل RMQ به LCA¶
در این جا از روی آرایه ورودی، یک درخت دکارتی می‌سازیم. درخت دکارتی یک درخت دودویی است که هر عضو آرایه متناظر با یک راس از درخت است. راس متناظر با عضو کمینه آرایه در ریشه قرار دارد، زیردرخت فرزند چپ معادل درخت دکارتی بازه ابتدا تا عضو کمینه و زیردرخت فرزند راست معادل درخت دکارتی بازه عضو کمینه تا انتها است. در شکل زیر یک درخت دکارتی را می‌بینید.
به کمک این مطلب که کوچکترین جد مشترک درون بازه بین این دو راس قرار دارد، ثابت کنید که برای پیدا کردن مینیمم در بازه، می توان پایین ترین جد مشترک در درخت دکارتی را پیدا کرد. در ادامه با ارائه یک راه از \(O(n)\) برای ساخت درخت دکارتی نشان می دهیم که اگر راهی برای RMQ وجود داشته باشد، راهی با همان پیچیدگی برای LCA وجود خواهد داشت.
ساخت درخت دکارتی در زمان خطی¶
درخت دکارتی را می‌توان به کمک یک استک ساخت. درون استک رئوسی که از پدرشان مطمئن نیستیم را به صورت مرتب (هم از لحاظ مقدار و هم از لحاظ مکان) نگه می‌داریم. ابتدا با استک خالی شروع کرده و شروع به پیمایش آرایه می کنیم. هر عضوی که می‌بینیم، تا جایی که از سر استک کوچک تر باشد را از استک حذف می کنیم. پدر همه آنها معلوم است. زیرا دیگر ممکن نیست کسی از جلوی آرایه پدر این رئوس باشد. پدر هر کدام راس قبلی در استک و پدر آخرین راس حذف شده همین راسی است که ورودی گرفته ایم. سپس این راس را درون استک اضافه می‌کنیم و به راس بعدی می‌رویم. در انتها یک جنگل به دست می آید که ریشه های آن درون استک است. این رئوس نیز به ترتیب هر کدام پدر راس قبلی است (چون دیگر راس جدیدی در کار نیست) و ریشه درخت نیز آخرین عضو استک است که کمینه آرایه نیز هست.
تبدیل LCA به RMQ¶
روی درخت DFS می‌زنیم. موقع ورود به هر راس، آن را در آرایه اضافه می کنیم و مقدار آن را برابر ارتفاع آن قرار می‌دهیم. موقع خروج از هر راس نیز پدر آن را به همین ترتیب به آرایه اضافه می‌کنیم. هر راس به تعداد فرزندانش به علاوه یک عضو متناظر در آرایه دارد. برای پیدا کردن پایین ترین جد مشترک، تنها کافیست که عضو کمینه بین اعضای متناظر دو راسی که می خواهیم LCA آن را به دست آوریم را محاسبه کرده و ببینیم که متناظر با چه راسی است. اثبات این مطلب به خواننده واگذار می‌شود. بنابراین اگر راهی برای یکی از مسائل LCA یا RMQ وجود داشته باشد برای دیگری نیز راهی با همان پیچیدگی وجود دارد.
حل مساله RMQ با جدول پراکنده¶
جدول پراکنده نوع خاصی از برنامه نویسی پویا است که در آن بعد دوم نسبت به بعد اول سایز لگاریتمی دارد. این جدول در مسائل مختلفی به کار می‌رود و در این جا به کمک آن این مساله را حل می‌کنیم. \(dp_{i,j}\) را برابر عضو کمینه در بازه \([i,i+2^j)\) باشد. اگر این dp را داشته باشیم به کمک آن می توان پرسش ها را در \(O(1)\) پاسخ داد. به این صورت که j را پیدا می کنیم که طول بازه مورد نظر بین \(2^j\) و \(2^{j+1}\) باشد. سپس جواب مساله برابر است با
محاسبه این جدول نیز از \(O(n*lg(n))\) امکان پذیر است. کافیست از j=۰ شروع کرده و تا لگاریتم طول آرایه جلو برویم. هر j به این صورت از j قبلی به دست می آید
به این ترتیب برای RMQ و LCA الگوریتمی از پیچیدگی زمانی \(O(n*lg(n)+q)\) داریم که در شرایطی که n از q کمتر باشد از الگوریتم قبلی \(O(n+q*lg(n))\) بهتر عمل می‌کند.
این کتاب توسط مشارکت کنندگان شاززز به وجود آمده است.
این کتاب عمومی است و تحت پروانه cc-by-sa در دسترس است.
آخرین به روز رسانی در ژوئن 09, 2022.
