مسائل جست و جوی بازه ای - range query

در هنر خطاطی تاکید می شود که یکی از راه های یادگیری خوش نویسی مشاهده آثار زیباست (مثلاً آثار میرعماد) ، به طور کلی یکی از راه های لمس بهتر هنر درک ، مشاهده و تعمق در آثار هنری است ( البته این یک گام از هزاران گام است) ، الگوریتم و ریاضیات نیز اگر به بعد هنری آن ها نگاه کنیم از این قاعده مستثنی نیستند ، گاهی اوقات شما یک مسئله خاص را حل  می کنید ولی می بینید شخص دیگری به روش بهتر ، زیباتر و تحسین برانگیز تری آن را حل کرده است 

هدف از پیش مقدمه بالا این است که به این نتیجه برسیم که آگاهی از مسائل مختلف و دسته ها و خانواده های آن ها دید بهتری به ما می دهد و باعث می شود هنگامی که با یک مسئله خاص مواجه می شویم راحت تر بتوانیم نوع مسئله و خانواده ای که مسئله به آن تعلق دارد را شناسایی کنیم . (البته ممکن است یک مسئله به بیش از یک خانواده تعلق داشته باشد).

در این آموزش با مسائلی به نام range query آشنا می شویم.

range query :

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

مسئله : آرایه ای متشکل از 200000 عدد صحیح مثبت به ما داده می شود روش حلی ارائه کنید که بتواند query زیر را به سرعت پاسخ دهد :

  • MAX i j : عنصر ماکسیمم بین بازه i تا j 

مثال :

ورودی : 


1 4 3 8 12 1 2 2 8 4 
MAX 1 1
MAX 1 10
MAX 2 3
MAX 3 5
MAX 4 9
MAX 6 8

پاسخ :


1
12
4
12
12
2

همانطور که در مثال بالا مشاهده کردید ترتیب اعداد وارد شده مهم است. 

تمرین : سعی کنید راه حل های مختلفی برای مسئله فوق ارائه کنید. (حالت های مختلف را در نظر بگیرید : اعداد وارد شده زیاد باشند ولی تعداد درخواست های از نوع MAX کم باشد ، اعداد وارد شده کم باشند ولی در خواست های از نوع MAX زیاد باشد ، هم اعداد وارد شده زیاد باشد و هم درخواست های از نوع MAX زیاد باشد)

در مثال قبل مشاهده کردید که ابتدا یک سری از اطلاعات به ما داده شد و سپس چندین درخواست صورت گرفت ، از این لحاظ مسائل range query را به دو خانواده می توان تقسیم کرد :

  1. مسائلی که داده های اولیه ثابت هستند ولی انتظار می رود درخواست ها به سرعت پاسخ داده شوند.
  2. مسائلی که داده ها ممکن است در طی زمان تغییر کنند که انتظار می رود هم راهکاری سریع برای تغییر داده ها و هم درخواست ها ارائه کنید.

مسئله : آرایه ای متشکل از 200000 عدد صحیح مثبت به ما داده می شود روش حلی ارائه کنید که بتواند query های زیر را به سرعت پاسخ دهد :

  • MAX i j : عنصر ماکسیمم بین بازه i تا j 
  • ADD i v : مقدار v را به داده i ام اضافه کند 

مثال :

ورودی :


1 4 3 8 12 1 2 2 8 4 
MAX 1 1
MAX 1 10
ADD 1 13
MAX 1 10
MAX 2 3
MAX 3 5
ADD 3 16
MAX 4 9
MAX 6 8
MAX 3 5

پاسخ :


1
12
14
4
12
12
2
19

نکته : پس از ارائه هر راه حل سعی کنید پیچیدگی زمانی راه حل خود را تحلیل کنید ، به عنوان مثال راه حل زیر یک راه حل بسیار ضعیف به حساب می آید (چرا؟) :

  • در هر بار فراخوانی پرس و جوی MAX  اعداد بازه i تا j را در یک لیست قرار دهیم ، لیست را به صورت نزولی مرتب کنیم ، عنصر اول لیست را استخراج کنیم.

حتی راه حل زیر نیز ضعیف به حساب می آید :

  • در هر بار فراخوانی پرس و جوی MAX با یک حلقه for عناصر بین i تا j را بررسی کنیم و عنصر بیشینه (ماکسیمم) را محسابه کنیم.

اگر دو راه حل فوق بسیار ضعیف و ضعیف به حساب می آیند راه حل مناسب باید دارای چه پیچیدگی زمانی باشد؟ 

نکته : در مثال قبل مشاهده کردید که دو نوع query داشتیم ، یکی تغییر دهنده (همان ADD در مثال قبلی) و یکی پرس و جو کننده (همان MAX در مثال قبلی). همچنین دقت کردیم که هر بار تغییر فقط یک خانه از آرایه مورد نظر را تغییر می دهد ولی هر query از نوع MAX یک بازه را مورد پرسش قرار می دهد. به چنین مسائلی poit-update,range-query گفته می شود.

سه دسته بندی مهم :

به صورت کلی مسائل خانواده range query را می توان به سه دسته بزرگ زیر تقسیم کرد :

  • point-update,range-query : تغییر به صورت نقطه ای ولی جست و جو به صورت بازه ای
  • range-update,point-query : تغییر به صورت بازه ای ، جست و جو به صورت نقطه ای
  • range-update,range-query : تغییر به صورت بازه ای ، جست و جو به صورت بازه ای (معمولاً (نه الزاماً همیشه) ، مسائل این خانواده سخت تر هستند).

مسئله : آرایه ای متشکل از 200000 عدد صحیح مثبت به ما داده می شود روش حلی ارائه کنید که بتواند query های زیر را به سرعت پاسخ دهد :

  • ADD i j v : به تمام اعداد بین i تا j مقدار v را اضافه کند.
  • GET i : مقدار مورد نظر در خانه i ام آرایه را بر گرداند.

یک راه حل بدیهی و ضعیف برای این مسئله به این شکل است که اعداد را در یک آرایه معمولی نگه داری کنیم ، متد ADD را به این شکل پیاده سازی کنیم که در یک حلقه for مقدار v را به عناصر بین i تا j اضافه کند. متد GET نیز به آسانی از طریق دسترسی به عنصر i ام آرایه امکان پذیر خواهد بود ، در این راه حل query های از نوع ADD از مرتبه $O(n)$ و query های از نوع GET از مرتبه $O(1)$ خواهند بود و اگر از شانس بد ما تعداد query های از نوع ADD زیاد باشد این راه حل ما را به هیچ جایی نخواهد رساند 

نکته : قبل از ادامه یکبار روی مسئله بالا فکر کنید ، اگر راه حل فوق ضعیف به حساب می آید چه راه حل بهتری می توان ارائه داد ؟ مثلاً راه حلی که query از نوع ADD در زمان $O(log(n))$ و query از نوع GET نیز در زمان $O(log(n))$ اجرا شود؟ آیا ارائه چنین راه حلی ممکن است؟ آیا باید دانسته هایمان را در مورد ساختمان داده ها افزایش دهیم؟ آیا ساختمان داده یا ساختمان داده های خاصی وجود دارند که پاسخ گوی این مسئله باشند؟

نکته  : همانطور که مشاهده کردید مسئله فوق از خانواده range-update,point-query بود.

مسئله :  آرایه ای متشکل از 200000 عدد صحیح مثبت به ما داده می شود روش حلی ارائه کنید که بتواند query های زیر را به سرعت پاسخ دهد

  • ADD i j v : به تمام اعداد بین i تا j مقدار v را اضافه کند.
  • MAX i j : مقدار ماکسیمم بین i تا j را محاسبه کند.

ورودی :


1 4 3 8 12 1 2 2 8 4 
MAX 1 1
MAX 1 10
ADD 6 8 11
MAX 1 10
MAX 2 3
ADD 1 4 6
MAX 3 5
ADD 5 5 8
MAX 1 10

خروجی :


1
12
13
4
14
20

نکته : مسئله فوق از نوع range-update,range-query بود.

نکته : در هنگام حل یک مسئله ممکن است بتوانید یک مسئله از نوع A را به مسئله ای از نوع B نگاشت دهید ، به عنوان ممکن است بتوانید یک مسئله از خانواده range-update,range-query را به مسئله ای از نوع range-update,point-query تقلیل دهید و آن را حل کنید (این جزئیات به راه حل شما بستگی دارند).

 

مسائل بیشتر :

در این قسمت قصد داریم مسائل بیشتری را با هم مشاهده کنیم.

min : 

بسیاری از مسائل range query مربوط به پیدا کردن مقدار مینیمم می شوند ، مطالعات زیادی بر روی مسائل مرتبط با این خانواده از مسائل انجام شده که به RMQ  مشهور هستند (Range Minimum Query) .

بسته به شرایط مسئله بهینه سازی های مختلفی نیز ارائه شده است.

مثال :

یک آرایه اولیه مشتکل از n (که معمولاً بزرگ است ، مثلاً 200000) به ما داده شده است ، می خواهیم query های زیر را به سرعت پاسخ دهیم :

  • MIN i j : مقدار مینیمم بین عناصر i تا j را بر گرداند.

نکته : در اینجا داده ها تغییر نمی کنند ، با یک پیش پردازش (pre-processing) در یک Parse Table از مرتبه زمانی $O(nlog(n))$ می توانیم query های از نوع MIN را با $O(1)$ پاسخ دهیم (در مورد این روش فکر کنید ، در مطالب بعدی مجدداً این موضوع را بررسی می کنیم).

مثال :

یک آرایه اولیه مشتکل از n (که معمولاً بزرگ است ، مثلاً 200000) به ما داده شده است ، می خواهیم query های زیر را به سرعت پاسخ دهیم :

  • MIN i j : مقدار مینیمم بین عناصر i تا j را بر گرداند.
  • SET i v : مقدار عنصر i ام را به v تغییر دهد.

روش های مختلفی برای حل این مسئله وجود دارد ، Segment Tree مشهور ترین ابزار حل این مسئله است ، ابتدا تصور می شد که BIT قادر به حل چنین مسائلی نیست که خلاف این موضوع نیز نمایش داده شد. مقاله عالی زیر این مسئله را با استفاده از BIT حل می کند.

http://ioinformatics.org/oi/pdf/v9_2015_39_44.pdf

مثال :

یک آرایه اولیه مشتکل از n (که معمولاً بزرگ است ، مثلاً 200000) به ما داده شده است ، می خواهیم query های زیر را به سرعت پاسخ دهیم :

  • MIN i j : مقدار مینیمم بین عناصر i تا j را بر گرداند.
  • ADD i j v : مقدار v را به عناصر بین i تا j اضافه می کند.

این مسئله نیز با Segment Tree قابل است ، برای غلبه بر کندی راه حل باید تکنیک lazy propagation را یاد بگیرید.

max :

مسائل مرتبط با max کمتر مطرح می شوند زیرا در مسائل بهینه سازی بیشتر به دنبال کمینه کردن هستیم. با این وجود تکنیک های فوق برای این خانواده از مسائل نیز قابل استفاده هستند.

mod :

mod عنصری است که بیشترین تکرار را در یک آرایه داشته باشد  ، mod range query مسئله ای است که از ما می خواهد تا عنصر با تکرار بیشتر را در بین عناصر i تا j پیدا کنیم.

median : 

median یا میانه عنصر میانی عناصر بین i تا j است در صورتی که عناصر i تا j را به صورت مرتب کنار هم قرار دهیم ، مطمئناً هر بار مرتب کردن آرایه i تا j پاسخگوی این مسئله نیست ، پیدا کردن میانه یکی از کاربردی ترین مسائل کامپیوتری است و در زمینه های مختلفی کاربرد دارد. برای حل این دسته از مسائل بهتر است با مفاهیمی همچون range tree آشنا باشید.

یک لینک عالی:

https://courses.csail.mit.edu/6.851/spring12/lectures/L03.html

sum :

پرکاربردترین خانواده از مسائل فوق است و به شکل های متفاوتی تغییر و ارائه می شود. حالت های مختلفی که برای min مطرح کردیم برای sum نیز قابل تعریف هستند.

 

فضاهای بزرگتر :

مسائلی که مطرح کردیم همگی مربوط به آرایه های یک بعدی بودند ولی مسائل range query محدود به آرایه های یک بعدی نیستند و قابل توسعه به حالت های دوبعدی ، سه بعدی و بیشتر نیز هستند.  

 

هندسه محاسباتی :

هندسه محاسباتی یکی از جالب ترین شاخته های علم کامپیوتری است که مسائلی به شکل query در آن بسیار مطرح می شوند ، با یادگیری هندسه محاسباتی با دریایی از مسائلی از نوع range query آشنا می شوید.

 

ابزار ها :

برای حمله به مسائل از نوع range query باید ابزار های زیادی را بشناسیم ، به واسطه مقالات و تحقیقاتی که در این زمینه های انجام می شود ساختمان داده ها و الگوریتم های زیادی ارائه می شود که ارائه لیست همه این ابزار ها در این مطلب امکان پذیر نیست ولی در ادامه سعی می کنم موارد مهم را بیان کنم و توصیه می کنم این موارد را مطالعه کنید و یاد بگیرید.

  • Segment Tree
  • Binary Indexed Tree
  • Red Black Tree
  • AVL Tree
  • Splay Tree
  • Scapegoat Tree
  • Treap
  • Sparse Table
  • SQRT Decomposition
  • Heap
  • Range Tree
  • Interval Tree
  • R Tree
  • Skip List

ساختمان داده ها و الگوریتم های بسیاری در رابطه با این گونه از مسائل وجود دارند که در صورت علاقه خودتان می توانید آن ها را نیز مطالعه کنید.

 

دیدگاه‌ها

1

عالی...خیلی جالب بود

افزودن دیدگاه جدید

Plain text

  • تگ‌های HTML مجاز نیستند.
  • نشانی صفحه‌ها وب و پست الکترونیک بصورت خودکار به پیوند تبدیل می‌شوند.
  • خطوط و پاراگراف‌ها بطور خودکار اعمال می‌شوند.