مقدمه
کار بر روی بازه های بزرگ ، شامل انجام بروز رسانی های تکراری و بدست آوردن یک مقدار برای یک بازه یکی از چالش های مطرح شده در علوم کامپیوتر است در این نوشتار سعی شده به بررسی داده ساختار پیشرفته ای به نام 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 مقایسه کاهش میدهد.

ادامه مطلب