جدول پراکنده

جدول پراکنده (به انگلیسی:sparse table) مفهومی است که برای جستجوی سریع در مجموعه ای از داده های استاتیک (داده هایی که تغییر نمی‌کنند) استفاده می شود و پیش پردازشی بر روی داده ها انجام می دهد تا به سوالات کاربر در ارتباط با داده ها پاسخ دهد.

تعریف

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

کاربرد ها

در این موارد می توان از جدول پراکنده کمک گرفت:

• جستجوی ماکسیمم بازه ای
• جستجوی بزرگترین مقسوم علیه مشترک بازه ای
• جستجوی مینیمم بازه ای
• جستجوی مجموع بازه ای

جستجوی ماکسیمم بازه ای

یکی از موارد استفاده جدول پراکنده در جستجوی ماکسیمم هر بازه مورد نیاز کاربر است. بدین صورت که:

آرایه ای مانند$A[0,...,n-1]$ را درنظر بگیرید، درهر مرحله یک بازه داده می شود که باید بزرگترین عدد در آن بازه را پیدا کرد. بازه های ما به شکل $Q=[L,R]$ هستند که L ابتدای بازه ی و R انتهای بازه را نشان می دهند و نیز این عبارت برای هر L و R برقرار است: $0\leq L\leq R\leq n-1$، به عنوان مثال آرایه $A=\{6,7,4,5,1,3\}$ را در نظر بگیرید که در بازه ی $Q1=[0,5]$ بزرگترین عدد 7 ، در بازه ی $Q2=[3,5]$ بزرگترین عدد 5 و در بازه $Q3=[2,4]$ نیز بزرگترین عدد 5 می باشد.

حال اگر تعداد بازه ها افزایش یابند این عمل نیازمند زمان زیادی است که بخواهیم تک تک اعداد آن بازه را بررسی کنیم ، به جای آن می توان از جدول پراکنده کمک گرفت و پاسخ هر بازه را بسیار سریع و در زمان $O(1)$ پیدا کرد.

ایده

می توان قبل از شروع پرسش داده هایمان را پیش پردازش کنیم و ماکسیمم تمامی زیرآرایه ها به طول $2^{j}$ که j در بازه 0 تا $\log n$ قرار دارد را بیابیم.

برای این کار یک جدول پراکنده به نام $lookup[i][j]$ ایجاد می کنیم که ماکسیمم تمامی بازه ها با شروع از i و به طول $2^{j}$ را در بردارد.برای پر کردن این جدول از طراحی پایین به بالا استفاده می کنیم و در مراحل بالاتر از نتایج مراحل پایین تر کمک می گیریم،به این صورت که برای یافتن ماکسیمم در بازه ی $[0,7]$ از ماکسیمم های دو بازه $[0,3]$ و $[4,7]$ استفاده میکنیم که بزرگترین آن ها ماکسیمم کل می باشد.

شبه کد زیر بیانگر مثال بالا است:

// 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]
   lookup[i][j] = lookup[i][j-1]

// If lookup[0][2] <lookup[4][2], 
// then lookup[0][3] = lookup[4][2]
Else 
   lookup[i][j] = lookup[i+2^(j-1)-1][j-1]

جدول جستجو

برای آرایه $A=\{7,2,3,0,5,10,3,12,18\}$ تمامی بازه های ممکن را در نظر می گیریم و جدول زیر را تکمیل میکنیم:

3	2	1	0	i/j
12	7	7	7	0
18	5	3	2	1
-	10	3	3	2
-	10	5	0	3
-	12	10	5	4
-	18	10	10	5
-	-	12	3	6
-	-	18	12	7
-	-	-	18	8

پس برای هر بازه$[L,R]$ از نزدیک ترین توان های 2 استفاده می کنیم،بدین صورت که دو بازه در نظر می گیریم که اولی $[L,L+closestPowerOf2]$ و دومی $[R-sameClosestPowerOf2+1,R]$ می باشد، درنهایت ماکسیمم کل که ماکسیمم این دو بازه است جواب مسئله می باشد.

شبه کد

شبه کد زیر نحوه یافتن ماکسیمم یک بازه به کمک دو زیر بازه از آن را به ما نشان می دهد:

// 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]
   min(L, R) = lookup[L][j]

// If lookup[2][3] <lookup[3][3], 
// then min(2, 10) = lookup[3][3]
Else 
   min(L, R) = lookup[i+2^(j-1)-1][j-1]

زمان اجرا

چون برای هر جستجو ما فقط یک مقایسه انجام می دهیم پس زمان بررسی هر درخواست $O(1)$ است.قبل از درخواست های کاربر پیش پردازشی روی داده ها صورت می گیرد که زمان اجرای آن $O(nlogn)$ است.

حافظه مصرفی

حافظه استفاده شده برای این الگوریتم $O(nlogn)$ است.

جستجوی بزرگترین مقسوم علیه مشترک بازه ای

یکی از کاربرد های دیگر جدول پراکنده یافتن بزرگترین مقسوم علیه مشترک در بازه مورد نیاز کاربر است:

آرایه ای مانند$A[0,...,n-1]$ را درنظر بگیرید، درهر مرحله یک بازه داده می شود که باید بزرگترین بزرگترین مقسوم علیه مشترک اعداد موجود در آن بازه را پیدا کرد. بازه های ما به شکل $Q=[L,R]$ هستند که L ابتدای بازه ی و R انتهای بازه را نشان می دهند و نیز این عبارت برای هر L و R برقرار است: $0\leq L\leq R\leq n-1$، به عنوان مثال آرایه $A=\{2,4,6,8,16,5\}$ را در نظر بگیرید که در بازه ی $Q1=[0,4]$ بزرگترین مقسوم علیه مشترک آنها 2، در بازه ی $Q2=[0,5]$ بزرگترین مقسوم علیه مشترک 1 و در بازه $Q3=[3,4]$ نیز بزرگترین مقسوم علیه مشترک 8 می باشد.

حال با افزایش تعداد بازه ها این عمل نیازمند زمان زیادی است که بخواهیم تک تک اعداد آن بازه را بررسی کنیم ، به جای آن می توان از جدول پراکنده کمک گرفت و پاسخ هر بازه را بسیار سریع و در زمان $O(1)$ پیدا کرد.

ایده

ایده این قسمت نیز همانند قسمت قبل است و با یک پیش پردازش روی داده ها و تعیین بزرگترین مقسوم علیه مشترک زیرآرایه هایی به طول $2^{j}$ که j در بازه 0 تا $\log n$ قرار دارد می توان در طول اجرای برنامه در زمان بسیار کمی پاسخ بازه مورد نظر را یافت.

پس یک جدول پراکنده$lookup[i][j]$ که شامل بزرگ ترین مقسوم علیه مشترک تمامی بازه ها با شروع از i و به طول $2^{j}$ است را ایجاد می کنیم و در هر مرحله از زیربازه های پایین تر برای تعیین بزرگترین مقسوم علیه مشترک بازه ی بالاتر شامل آن دو بازه استفاده می کنیم،بدین صورت که بزرگترین مقسوم علیه مشترک اعداد بازه بزرگتر همان بزرگترین مقسوم علیه مشترک پاسخ بازه های کوچکتر است که در مراحل قبل یافتیم.

جدول جستجو

برای آرایه $A=\{7,2,3,0,5,10,3,12,18\}$ جدول جستجو به صورت زیر می باشد:

3	2	1	0	i/j
1	1	1	7	0
1	1	1	2	1
-	1	3	3	2
-	1	5	0	3
-	1	5	5	4
-	1	1	10	5
-	-	3	3	6
-	-	6	12	7
-	-	-	18	8

زمان و حافظه مصرفی

همانطور که در بخش قبل نیز توضیح داده شد،زمان اجرا(پیش پردازش) و حافظه استفاده شده برای این عمل $O(nlogn)$ است و زمان لازم برای پاسخ به هر پرسش $O(1)$ است.

جستجوی مینیمم بازه ای

از کاربرد های دیگر درخت پراکنده می توان به جستجوی مینیمم بازه ای اشاره کرد:

جستجوی مینیمم بازه ای

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

زمان پیش پردازش،پاسخ به هر پرسش و حافظه مصرفی همانند موارد قبل است.

جدول جستجو

برای آرایه $A=\{7,2,3,0,5,10,3,12,18\}$ جدول جستجو به صورت زیر خواهد بود:

3	2	1	0	i/j
0	0	2	7	0
0	0	2	2	1
-	0	0	3	2
-	0	0	0	3
-	3	5	5	4
-	3	3	10	5
-	-	3	3	6
-	-	12	12	7
-	-	-	18	8

جستجوی مجموع بازه ای

کاربرد دیگری که می توان برای درخت پراکنده نام برد،استفاده از آن در جستجوی مجموع بازه ای است.

روشی که درخت پراکنده در اختیار ما می گذارد همانند روش هایی است که در بالا ذکر شد فقط باید در تمامی زیرآرایه ها به طول $2^{j}$ که j در بازه 0 تا $\log n$ قرار دارد مجموع اعداد آن بازه را در درخت پراکنده ذخیره کنیم و پیش پردازش را به این صورت انجام دهیم. با استفاده از این روش میتوان به هر سوالی که در رابطه با مجموع اعداد بازه های مختلف پرسیده می شود در $O(1)$ پاسخ داد.

ایده کلی ، زمان و حافظه مصرفی این مسائل نیز مثل تمامی مسائل بالاست.

جدول جستجو

برای آرایه $A=\{7,2,3,0,5,10,3,12,18\}$ جدول جستجو به صورت زیر است:

3	2	1	0	i/j
42	12	9	7	0
53	10	5	2	1
-	18	3	3	2
-	18	5	0	3
-	30	15	5	4
-	43	13	10	5
-	-	15	3	6
-	-	30	12	7
-	-	-	18	8

منابع

• Sparse Table
• Range Maximum Query
• Sparse table data structure
• Range sum query