جدول پراکنده
جدول پراکنده (به انگلیسی:sparse table) مفهومی است که برای جستجوی سریع در مجموعه ای از داده های استاتیک (داده هایی که تغییر نمی‌کنند) استفاده می شود و پیش پردازشی بر روی داده ها انجام می دهد تا به سوالات کاربر در ارتباط با داده ها پاسخ دهد.
یک آرایه را در نظر بگیرید شامل n عضو از یک مجموعه منظم(خوش ترتیب) مانند مجموعه اعداد باشد،می توان به کمک یک جدول پراکنده درهرمرحله طبق خواسته کاربر خروجی مورد نیاز او را بدون نیاز به صرف زمان زیاد چاپ کرد. خواسته کاربر می تواند موارد مختلفی را شامل شود که به تفکیک هرکدام را بررسی خواهیم کرد.
در این موارد می توان از جدول پراکنده کمک گرفت: یکی از موارد استفاده جدول پراکنده در جستجوی ماکسیمم هر بازه مورد نیاز کاربر است. بدین صورت که:
آرایه ای مانندformula_1 را درنظر بگیرید، درهر مرحله یک بازه داده می شود که باید بزرگترین عدد در آن بازه را پیدا کرد. بازه های ما به شکل formula_2 هستند که L ابتدای بازه ی و R انتهای بازه را نشان می دهند و نیز این عبارت برای هر L و R برقرار است: formula_3، به عنوان مثال آرایه formula_4 را در نظر بگیرید که در بازه ی formula_5 بزرگترین عدد 7 ، در بازه ی formula_6 بزرگترین عدد 5 و در بازه formula_7 نیز بزرگترین عدد 5 می باشد.
حال اگر تعداد بازه ها افزایش یابند این عمل نیازمند زمان زیادی است که بخواهیم تک تک اعداد آن بازه را بررسی کنیم ، به جای آن می توان از جدول پراکنده کمک گرفت و پاسخ هر بازه را بسیار سریع و در زمان formula_8 پیدا کرد.
می توان قبل از شروع پرسش داده هایمان را پیش پردازش کنیم و ماکسیمم تمامی زیرآرایه ها به طول formula_9 که j در بازه 0 تا formula_10 قرار دارد را بیابیم.
برای این کار یک جدول پراکنده به نام formula_11 ایجاد می کنیم که ماکسیمم تمامی بازه ها با شروع از i و به طول formula_9 را در بردارد.برای پر کردن این جدول از طراحی پایین به بالا استفاده می کنیم و در مراحل بالاتر از نتایج مراحل پایین تر کمک می گیریم،به این صورت که برای یافتن ماکسیمم در بازه ی formula_13 از ماکسیمم های دو بازه formula_14 و formula_15 استفاده میکنیم که بزرگترین آن ها ماکسیمم کل می باشد.
شبه کد زیر بیانگر مثال بالا است: // Maximum of single element subarrays is same // as the only element. lookup[i][0] = arr[i]
// If lookup[0][2]>= lookup[4][2],  // then lookup[0][3] = lookup[0][2] If lookup[i][j-1]>= lookup[i+2^(j-1)-1][j-1]
// If lookup[0][2]
برای آرایه formula_16 تمامی بازه های ممکن را در نظر می گیریم و جدول زیر را تکمیل میکنیم:
پس برای هر بازهformula_17 از نزدیک ترین توان های 2 استفاده می کنیم،بدین صورت که دو بازه در نظر می گیریم که اولی formula_18 و دومی formula_19 می باشد، درنهایت ماکسیمم کل که ماکسیمم این دو بازه است جواب مسئله می باشد.
شبه کد زیر نحوه یافتن ماکسیمم یک بازه به کمک دو زیر بازه از آن را به ما نشان می دهد: // For (2, 10), j = floor(Log(10-2+1)) = 3 j = floor(Log(R-L+1))
// If lookup[2][3]>= lookup[3][3],  // then min(2, 10) = lookup[2][3] If lookup[L][j]>= lookup[R-(int)pow(2, j)+1][j]
// If lookup[2][3]
چون برای هر جستجو ما فقط یک مقایسه انجام می دهیم پس زمان بررسی هر درخواست formula_8 است.قبل از درخواست های کاربر پیش پردازشی روی داده ها صورت می گیرد که زمان اجرای آن formula_21 است.
حافظه استفاده شده برای این الگوریتم formula_21 است.
یکی از کاربرد های دیگر جدول پراکنده یافتن بزرگترین مقسوم علیه مشترک در بازه مورد نیاز کاربر است:
آرایه ای مانندformula_1 را درنظر بگیرید، درهر مرحله یک بازه داده می شود که باید بزرگترین بزرگترین مقسوم علیه مشترک اعداد موجود در آن بازه را پیدا کرد. بازه های ما به شکل formula_2 هستند که L ابتدای بازه ی و R انتهای بازه را نشان می دهند و نیز این عبارت برای هر L و R برقرار است: formula_3، به عنوان مثال آرایه formula_26 را در نظر بگیرید که در بازه ی formula_27 بزرگترین مقسوم علیه مشترک آنها 2، در بازه ی formula_28 بزرگترین مقسوم علیه مشترک 1 و در بازه formula_29 نیز بزرگترین مقسوم علیه مشترک 8 می باشد.
حال با افزایش تعداد بازه ها این عمل نیازمند زمان زیادی است که بخواهیم تک تک اعداد آن بازه را بررسی کنیم ، به جای آن می توان از جدول پراکنده کمک گرفت و پاسخ هر بازه را بسیار سریع و در زمان formula_8 پیدا کرد.
ایده این قسمت نیز همانند قسمت قبل است و با یک پیش پردازش روی داده ها و تعیین بزرگترین مقسوم علیه مشترک زیرآرایه هایی به طول formula_9 که j در بازه 0 تا formula_10 قرار دارد می توان در طول اجرای برنامه در زمان بسیار کمی پاسخ بازه مورد نظر را یافت.
پس یک جدول پراکندهformula_11 که شامل بزرگ ترین مقسوم علیه مشترک تمامی بازه ها با شروع از i و به طول formula_9 است را ایجاد می کنیم و در هر مرحله از زیربازه های پایین تر برای تعیین بزرگترین مقسوم علیه مشترک بازه ی بالاتر شامل آن دو بازه استفاده می کنیم،بدین صورت که بزرگترین مقسوم علیه مشترک اعداد بازه بزرگتر همان بزرگترین مقسوم علیه مشترک پاسخ بازه های کوچکتر است که در مراحل قبل یافتیم.
برای آرایه formula_16 جدول جستجو به صورت زیر می باشد:
همانطور که در بخش قبل نیز توضیح داده شد،زمان اجرا(پیش پردازش) و حافظه استفاده شده برای این عمل formula_36 است و زمان لازم برای پاسخ به هر پرسش formula_37 است.
از کاربرد های دیگر درخت پراکنده می توان به جستجوی مینیمم بازه ای اشاره کرد:در این روش نیز همانند دو قسمت قبل پیش پردازش را روی داده ها انجام می دهیم و مشابه قسمت اول عمل میکنیم با این تفاوت که بجای یافتن ماکسیمم در هر بازه مینیمم آن بازه را می یابیم و در جدول وارد می کنیم وسپس طبق پرسش مورد نظر به هر سوال در زمان کمتری پاسخ می دهیم.
زمان پیش پردازش،پاسخ به هر پرسش و حافظه مصرفی همانند موارد قبل است.
برای آرایه formula_16 جدول جستجو به صورت زیر خواهد بود:
کاربرد دیگری که می توان برای درخت پراکنده نام برد،استفاده از آن در جستجوی مجموع بازه ای است.
روشی که درخت پراکنده در اختیار ما می گذارد همانند روش هایی است که در بالا ذکر شد فقط باید در تمامی زیرآرایه ها به طول formula_9 که j در بازه 0 تا formula_10 قرار دارد مجموع اعداد آن بازه را در درخت پراکنده ذخیره کنیم و پیش پردازش را به این صورت انجام دهیم. با استفاده از این روش میتوان به هر سوالی که در رابطه با مجموع اعداد بازه های مختلف پرسیده می شود در formula_8 پاسخ داد.
ایده کلی ، زمان و حافظه مصرفی این مسائل نیز مثل تمامی مسائل بالاست.
برای آرایه formula_16 جدول جستجو به صورت زیر است: