DemoVersion
مقدمه
کار بر روی بازه های بزرگ ، شامل انجام بروز رسانی های تکراری و بدست آوردن یک مقدار برای یک بازه یکی از چالش های مطرح شده در علوم کامپیوتر است در این نوشتار سعی شده به بررسی داده ساختار پیشرفته ای به نام 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 مقایسه کاهش میدهد.
کجا میتوان Segment Tree را مطرح کرد؟
Segment Tree را میتوان در هر مسئله ای که شکستن بازه یا پرانتز بندی سازگار باشد مطرح کرد. برای مثال ماکزیمم ، مینیمم ، ضرب کل اعداد بازه ، مجموع کل اعداد بازه ، بزرگترین مقسوم علیه کل اعداد یک بازه و...
ممکن است برخی از این مسائل از روش برنامه نویسی پویا یا Dynamic Programming که پیش از این مطرح شد نیز قابل حل باشد در آن صورت نیاز است که چهار هزینه ساخت اولیه ، نگه داری ( مصرف حافظه ) ، بروز رسانی و پیدا کردن مقدار در شرایط مسئله بررسی شود و روش بصرفه را انتخاب کنیم.
داده ها در Segment Tree چگونه ذخیره میشوند؟
برای ذخیره داده ها به یک درخت دو دویی نیاز داریم ، حالت معمول درخت دودویی استفاده از یک Struct یا Class و دو Pointer میباشد که حتما آشنایی دارید ، برای درخت های دو دو دویی نحوه نمایش دیگری نیز وجود دارد و آن نگه داری کل محتوا در یک آرایه میباشد که اگر تعداد عنصر های درخت قابل پیشبینی باشد و درخت متقارن باشد مصرف حافظه به علت عدم نیاز به Pointer های اضافی به اندازه چشم گیری کاهش پیدا میکند ، این دو شرط کاملا برای Segment Tree سازگار است و در اکثر مواقع از یک آرایه برای ذخیره اطلاعات Segment Tree استفاده میشود.
در Segment Tree به یک آرایه حدود 4 برابر طول بازه نیاز داریم. و اطلاعات به شکل زیر ذخیره میشود
مقدار مربوط به کل بازه در خانه شماره 1
و به ازای هر بازه که به آن خانه ای از آرایه به شماره K نسبت داده شده ، مقدار نیمه اول بازه در 2*K و مقدار نیمه دوم بازه در K*2+1 ذخیره میشود.
به تصویر توجه کنید
چگونه Segment Tree بسازیم ؟ ( Build Method )
ساخت اولیه در کنار بروز رسانی و بدست آوردن محتوا یکی از سه عملیاتی است که میبایست برای Segment Tree تعریف کنیم.
ساخت اولیه درخت بازه ای دارای مرتبه زمانی Nlog(N) میباشد.
ایده ساخت یک ایده بازگشتی میباشد ، به این صورت که ابتدا برای نیمه اول تابع ساخت صدا زده میشود ، سپس برای نیمه دوم صدا زده میشود و بعد از به اتمام رسیدن این دو تابع بر حسب مقدار این دو تابع مقدار بازه محاسبه میشود.
برای مثال اگر Segment Tree برای نگه داری مقدار بیشینه یک بازه باشد ، مقدار بیشینه نیمه اول بازه را محاسبه میکنیم سپس مقدار نیمه دوم ، حال مقدار بیشینه کل بازه را میتوان بیشینه نیمه اول و نیمه دوم تعریف کرد، شرط توقف در این بازگشتی وقتی است که به اندازه ای بازه کوچک شود که تنها یک خانه در بازه مورد نظر بگنجد.
به ازای 4 عدد 16 ، 21 ، 53 ، 77 درخت بازه ای به شکل زیر میشود.
بدست آوردن مقدار یک بازه چگونه است؟ ( Get Method )
برای اینکار ما نوعی از Segment Tree را مورد بررسی قرار میدهیم که در آن تغییرات در یک خانه انجام میشود و خواندن مقدار در یک بازه ، عکس این نوع نیز با کمی تغییر در این دو تابع قابل استفاده است ، اما نوع تغییر در بازه و خواندن مقدار در یک بازه که کمتر مورد استفاده قرار میگیرد دارای پیچیده گی بیشتری به نسبت میباشد.
بدست آوردن مقدار دارای مرتبه زمانی Log(N) می باشد، و ایده بازگشتی آن به شکل زیر تعریف میشود:
میخواهیم مقدار بیشینه را برای بازه a تا b در Segment Tree ای بدست آوریم که با بازه L تا R ساخته شده است، بدیهی است که میبایست در ابتدایی ترین فراخوانی زیر بازه L تا R باشد.
در هر بار صدا زدن میتواند سه حالت رخ دهد.
L تا R جدید زیر بازه a تا b شده باشد ، پس مقدار ذخیره شده به عنوان بخشی از بازه بر میگردد تا ترکیب شود.
L تا R جدید هیچ برهم نهی ای با a تا b نداشته باشد. کوچک ترین مقدار ممکن برمیگردد.
اگر دو حالت بالا نبود.
باید L تا R جدید دوباره از وسط شکسته شود ، و پس از دو فراخوانی برای دو نیمه بازه ، مقدار بیشینه این دو برگردانده شود.
توجه کنید که در کل فراخوانی ها بازه a تا b ثابت مانده است.
شکل قبل را در نظر بگیرید ، برای مثال میخواهیم از بازه 1 تا 3 بیشینه را پیدا کنیم. R تا L اولیه ما 1 تا 4 بود به دو قسمت شکسته میشود به ازای نیمه اول ، چون زیر مجموعه a تا b شده است مقدار نیمه اول بر میگردد ، برای نیمه دوم دوباره شکسته میشود ،
مقداری که برای ربع سوم برمیگردد 53 است
برای ربع چهارم علت این که خارج از بازه a تا b است مقدار 0 بر گشت داده میشود.
بیشینه این دو 53 به سطح اول برمیگردد.
و مقداری که در نهایت برمیگردد بیشینه 53 و 21 است.
بروز رسانی یک خانه چطور انجام میشود ؟ ( Update Method )
بروز رسانی یک خانه دارای مرتبه زمانی Log(N)بوده و برای مثال برای مسئله بیشینه به صورت زیر انجام میشود.
اگر L تا R جدید شامل i نبود باید بدون هیچ کاری بازگشت انجام بپذیرد.
اگر L تا R جدید شامل i بود
باید با شکستن از وسط بازه ، بیشینه های جدید را پیدا کرده و مقدار این بازه را بروز کنیم.
برای مثال میخواهیم در خانه 4 مقدار 77 را به 35 تغییر دهیم.
به سه تصویر زیر که به ترتیب مراحل انجام این تغییر را نشان میدهد توجه کنید
۸ مهر ۹۳، ۲۰:۲۱
دمت گرم حاجی!
برای این مبحث که اکثر منابع انگلیسی هستن، خیلی لازم بودش این کار شوما :-"