موضوع مقاله: جدول پراکنده | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # جدول پراکنده | مقدمه: جدول پراکنده (به انگلیسی:sparse table) مفهومی است که برای جستجوی سریع در مجموعه ای از داده های استاتیک (داده هایی که تغییر نمی‌کنند) استفاده می شود و پیش پردازشی بر روی داده ها انجام می دهد تا به سوالات کاربر در ارتباط با داده ها پاسخ دهد. | ## بخش 1: جدول پراکنده | تعریف یک آرایه را در نظر بگیرید شامل n عضو از یک مجموعه منظم(خوش ترتیب) مانند مجموعه اعداد باشد،می توان به کمک یک جدول پراکنده درهرمرحله طبق خواسته کاربر خروجی مورد نیاز او را بدون نیاز به صرف زمان زیاد چاپ کرد. خواسته کاربر می تواند موارد مختلفی را شامل شود که به تفکیک هرکدام را بررسی خواهیم کرد. کاربرد ها در این موارد می توان از جدول پراکنده کمک گرفت: جستجوی ماکسیمم بازه ای جستجوی بزرگترین مقسوم علیه مشترک بازه ای جستجوی مینیمم بازه ای جستجوی مجموع بازه ای جستجوی ماکسیمم بازه ای یکی از موارد استفاده جدول پراکنده در جستجوی ماکسیمم هر بازه مورد نیاز کاربر است. بدین صورت که: آرایه ای مانند را درنظر بگیرید، درهر مرحله یک بازه داده می شود که باید بزرگترین عدد در آن بازه را پیدا کرد. بازه های ما به شکل هستند که L ابتدای بازه ی و R انتهای بازه را نشان می دهند و نیز این عبارت برای هر L و R برقرار است: ، به عنوان مثال آرایه را در نظر بگیرید که در بازه ی بزرگترین عدد 7 ، در بازه ی بزرگترین عدد 5 و در بازه نیز بزرگترین عدد 5 می باشد. حال اگر تعداد بازه ها افزایش یابند این عمل نیازمند زمان زیادی است که بخواهیم تک تک اعداد آن بازه را بررسی کنیم ، به جای آن می توان از جدول پراکنده کمک گرفت و پاسخ هر بازه را بسیار سریع و در زمان پیدا کرد. | ## بخش 2: جدول پراکنده | ایده می توان قبل از شروع پرسش داده هایمان را پیش پردازش کنیم و ماکسیمم تمامی زیرآرایه ها به طول که j در بازه 0 تا قرار دارد را بیابیم. برای این کار یک جدول پراکنده به نام ایجاد می کنیم که ماکسیمم تمامی بازه ها با شروع از i و به طول را در بردارد.برای پر کردن این جدول از طراحی پایین به بالا استفاده می کنیم و در مراحل بالاتر از نتایج مراحل پایین تر کمک می گیریم،به این صورت که برای یافتن ماکسیمم در بازه ی از ماکسیمم های دو بازه و استفاده میکنیم که بزرگترین آن ها ماکسیمم کل می باشد. جستجوی بزرگترین مقسوم علیه مشترک بازه ای یکی از کاربرد های دیگر جدول پراکنده یافتن بزرگترین مقسوم علیه مشترک در بازه مورد نیاز کاربر است: آرایه ای مانند را درنظر بگیرید، درهر مرحله یک بازه داده می شود که باید بزرگترین بزرگترین مقسوم علیه مشترک اعداد موجود در آن بازه را پیدا کرد. بازه های ما به شکل هستند که L ابتدای بازه ی و R انتهای بازه را نشان می دهند و نیز این عبارت برای هر L و R برقرار است: ، به عنوان مثال آرایه را در نظر بگیرید که در بازه ی بزرگترین مقسوم علیه مشترک آنها 2، در بازه ی بزرگترین مقسوم علیه مشترک 1 و در بازه نیز بزرگترین مقسوم علیه مشترک 8 می باشد. حال با افزایش تعداد بازه ها این عمل نیازمند زمان زیادی است که بخواهیم تک تک اعداد آن بازه را بررسی کنیم ، به جای آن می توان از جدول پراکنده کمک گرفت و پاسخ هر بازه را بسیار سریع و در زمان پیدا کرد. ایده ایده این قسمت نیز همانند قسمت قبل است و با یک پیش پردازش روی داده ها و تعیین بزرگترین مقسوم علیه مشترک زیرآرایه هایی به طول که j در بازه 0 تا قرار دارد می توان در طول اجرای برنامه در زمان بسیار کمی پاسخ بازه مورد نظر را یافت. | ## بخش 3: جدول پراکنده | پس یک جدول پراکنده که شامل بزرگ ترین مقسوم علیه مشترک تمامی بازه ها با شروع از i و به طول است را ایجاد می کنیم و در هر مرحله از زیربازه های پایین تر برای تعیین بزرگترین مقسوم علیه مشترک بازه ی بالاتر شامل آن دو بازه استفاده می کنیم،بدین صورت که بزرگترین مقسوم علیه مشترک اعداد بازه بزرگتر همان بزرگترین مقسوم علیه مشترک پاسخ بازه های کوچکتر است که در مراحل قبل یافتیم. جدول جستجو برای آرایه جدول جستجو به صورت زیر می باشد: +3210i/j1117011121-1332-1503-1554-11105--336--6127 188 زمان و حافظه مصرفی همانطور که در بخش قبل نیز توضیح داده شد،زمان اجرا(پیش پردازش) و حافظه استفاده شده برای این عمل است و زمان لازم برای پاسخ به هر پرسش است. جدول جستجو برای آرایه جدول جستجو به صورت زیر خواهد بود: +3210i/j0027000221-0032-0003-3554-33105--336--12127 188 جستجوی مجموع بازه ای کاربرد دیگری که می توان برای درخت پراکنده نام برد،استفاده از آن در جستجوی مجموع بازه ای است. روشی که درخت پراکنده در اختیار ما می گذارد همانند روش هایی است که در بالا ذکر شد فقط باید در تمامی زیرآرایه ها به طول که j در بازه 0 تا قرار دارد مجموع اعداد آن بازه را در درخت پراکنده ذخیره کنیم و پیش پردازش را به این صورت انجام دهیم. | ## جمع‌بندی | با استفاده از این روش میتوان به هر سوالی که در رابطه با مجموع اعداد بازه های مختلف پرسیده می شود در پاسخ داد.