مسابقه‌ی بین‌المللی برنامه‌سازی دانش‌جویی

این صفحه فقط خواندنی است. شما می‌توانید متن صفحه را مشاهده کنید، اما نمی‌توانید آن را تغییر دهید. اگر فکر می‌کنید که مشکلی رخ داده است، مدیر ویکی را در جریان بگذارید.

====== پرس‌و‌جوی بازه‌ای ======
انواع مختلفی از پرس‌وجوی بازه‌ای وجود دارد که برای هر کدام ساختمان‌داده‌های مناسب وجود دارند.
  * پیدا کردن بازه‌های شامل یک نقطه: درخت پاره‌خط‌ها
  * اختصاص دادن مقادیر به بازه‌ها و پیدا کردن مجموع: درخت فنویک
  * پیدا کردن مقدار کمینه در یک بازه = پایین‌ترین جد مشترک: [[الگوریتم:برنامه‌ریزی_پویا|برنامه‌ریزی پویا]]، درخت پاره‌خط‌ها
===== درخت پاره‌خط‌ها =====
به ازای بازه‌های داده شده، سرهای بازه‌ها را مرتب می‌کنیم. این نقاط بازه‌هایی روی محور اعداد ایجاد می‌کنند که یک افراز هستند (اشتراک ندارند). این بازه‌ها برگ‌های درخت پاره‌خط‌ها هستند. روی این بازه‌ها یک درخت می‌سازیم. سپس بازه‌های ورودی مسأله را در گره‌های درخت طوری قرار می‌دهیم که در بالاترین گره‌ای باشند که شامل هیچ بازه‌ای خارج از بازه‌ی مورد نظر نیست.

برای پیدا کردن یک نقطه، روی درخت طوری پایین می‌رویم که بازه‌ی متناظر آن گره شامل این نقطه باشد. همه‌ی بازه‌هایی که در گره‌های موجود در این مسیر هستند، جواب مسأله هستند.

زمان پرس‌و‌جو $O(k \log n)$ است که $n$ تعداد بازه‌های اولیه و $k$ تعداد بازه‌های شامل آن نقطه است. زمان ساخت درخت هم $O(n \log n)$ است.

برای حل مسأله‌ی مقدار کمینه در یک بازه، ابتدا مقدار کمینه در هر بازه‌ی موجود در برگ را حساب می‌کنیم و به همین صورت مقدار کمینه هر بازه بزرگتر را در گره‌ها نگه می‌داریم. در این صورت مسأله تبدیل به همین مسأله‌ی پیدا کردن بازه می‌شود.

برای حل مسأله‌ی پایین‌ترین جد مشترک دو رأس $u$ و $v$ در درخت می‌توان رأسها را در برگ‌ها گذاشت و همان روش جستجوی درخت پاره‌خط‌ها را اجرا کرد.
==== درخت پاره‌خط‌های ۲-بعدی ====
ساخت این درخت ساده است. ابتدا روی محور $x$ تصویر می‌کنیم و یک درخت یک بعدی می‌سازیم، سپس به ازای هر بازه در برگ درخت پاره‌خط‌ها، یک درخت پاره‌خط‌ها به ازای تصویر روی محور $y$ می‌سازیم.

زمان ساخت درخت $O(n\log^2 n)$ و زمان پرس‌و‌جو $O(\log^2 n)$ است.

[[http://help.topcoder.com/data-science/competing-in-algorithm-challenges/algorithm-tutorials/range-minimum-query-and-lowest-common-ancestor/#Segment_Trees|مطالب بیشتر در مورد درخت پاره‌خط‌ها]]
===== درخت فنویک =====
در رأسهای این درخت، فراوانی‌های تجمعی نگهداری می‌شوند و پرس‌و‌جوها به صورت افزایش تعداد یک شئ و محاسبه‌ی تعداد اشیای یک بازه است. ساختار این درخت بر اساس نمایش دودویی اعداد است و هر رأس پدر رأسهایی است که با حذف آخرین بیت غیرصفرشان به آن رأس تبدیل می‌شوند.

زمان ساخت این درخت $O(n\log n)$ و زمان پرس‌و‌جوی آن $O(\log n)$ است.

این درخت را می‌توان به صورت ۲-بعدی هم پیاده‌سازی و استفاده کرد. این درخت را با نام $Binary\ Indexed\ Tree$ هم می‌شناسند و پیاده‌سازی از آن در [[آماده‌سازی:کدهای_آماده|کدهای آماده]] وجود دارد.

[[http://fa.wikipedia.org/wiki/%D8%AF%D8%B1%D8%AE%D8%AA_%D9%81%D9%86%D9%88%DB%8C%DA%A9|مطالب بیشتر درباره درخت فنویک در ویکی‌پدیا]]

[[http://help.topcoder.com/data-science/competing-in-algorithm-challenges/algorithm-tutorials/binary-indexed-trees/|مطالب بیشتر درباره درخت فنویک]]

مسابقه‌ی بین‌المللی برنامه‌سازی دانش‌جویی

ابزار کاربر

ابزار سایت

ابزار صفحه