حسام حداد تکنولوژی، برنامه‌نویسی، هوش مصنوعی

مقدمه
قبل از این داده ساختار Segment Tree را به صورت تئوری مورد بحث قرار دادیم ، امروز مسئله UVA 12086 - Potentiometers یا مقاومت متغییر که با استفاده از این ساختمان داده قابل حل میباشد را پیاده سازی میکنیم.

متن مسئله
PDF مسئله از اینجا قابل دریافت است ، خلاصه متن این است که N مقاومت متغییر روی یک خط قرار گرفتند ، و مقدار اولیه هریک را داریم ، باید به تعداد M دستور پاسخ بدهیم دو نوع دستور داریم
نوع اول : مقدار مقاومت x را به r تغییر بده
نوع دوم : مقاومت معادل r تا l را چاپ کن ، که معادل با جمع تک تک مقاومت های این بازه میباشد.

راه حل
ابتدا راه حل ساده یعنی پیاده سازی همین کار با دو حلقه تو در تو به نظر درست می آید اما مرتبه این الگوریتم O(NM) میباشد که با توجه اینکه N میتواند تا 200000 باشد ، و M نیز میتواند تا 200000 باشد بطور تقریبی میتوان حدس زد که این الگوریتم نیاز به زمان اجرای 400 ثانیه ای تنها برای یک تست دارد و نتیجه این ارسال بدون شک Time Limit Executed میباشد ، برنامه میبایست زیر 3 ثانیه تمامی دستورات تمام تست ها را پاسخ گو باشد. 

مقدمه
کار بر روی بازه های بزرگ ، شامل انجام بروز رسانی های تکراری و بدست آوردن یک مقدار برای یک بازه یکی از چالش های مطرح شده در علوم کامپیوتر است در این نوشتار سعی شده به بررسی داده ساختار پیشرفته ای به نام Segment Tree پرداخته شود که در مسائلی که قابلیت مطرح شدن دارد میتواند بسیار سریع ظاهر شود همچنین داده ساختار دیگری با نام  Sqrt Decomposition وجود دارد که کاربردی شبیه به Segment Tree دارد.

Segment Tree چیست؟
به بیان ساده میتوان گفت Segment Tree خلاصه کردن دو دویی یک بازه میباشد.
فرض کنید یک آرایه از 10000 ساختمان به ترتیب نامشخص که در یک ردیف قرار گرفته اند را داریم. میخواهیم در یک بازه از a تا b بلند ترین ساختمان را پیدا کنیم، ما از قبل میدانیم که بلند ترین ساختمان در 5000 ساختمان اول کدام است.  به عبارت دیگر بیشینه  بازه 1 تا 5000 را داریم ، چه استفاده ای میتوانیم از بیشینه این بازه کنیم؟ جواب ساده است اگر 1 تا 5000 زیر بازه بازه انتخابی بود میتوانیم از جستجو در این بخش صرف نظر کنیم و از مقدار ذخیره شده استفاده کنیم.
برای مثال بازه 1 تا 7000 را در نظر بگیرید. کافیست بیشینه ذخیره شده را با بیشینه بازه 5001 تا 7000 مقایسه کنیم. در این مثال نسبت به الگوریتم اولیه ( جستجو از a تا b برای پیدا کردن بیشینه ) 5000 مقایسه را صرف نظر کرده ایم زیرا بلند ترین ساختمان 5000 خانه اول را میدانیم و کافیست این مقدار را با 2000 ساختمان بعدی مقایسه کنیم.
این یک مثال ساده بود در عمل در Segment Tree بازه های خیلی بیشتری با یک نظم دو دویی ذخیره میشود و در بدترین حالت ممکن تعداد مقایسه ها به Log(N) میرسد که بسیار در مقایسه با N قابل توجه میباشد.
در مثال بالا الگوریتم اولیه در بدترین حالت مقدار 10000 مقایسه را انجام می دهد اما استفاده از Segment Tree این مقدار را در بدترین حالت به 14 مقایسه کاهش میدهد.