payamvha/North_RAG huggingface dataset:
اندیس‌هایی که در تمام لیست‌ها باید تغییر کند، عدد بسیار بزرگی خواهد بود. برای همین، در این مدل، داده ساختارهای دیگری برای ذخیره شدن در هر گره، در نظر گرفته می‌شود که به شرح زیر می‌باشند: این داده ساختارها باعث می‌شوند که آبشاره‌سازی پویا در مرتبهٔ زمانی (O(log n برای هر درج و حذف عمل کند. همچنین یک زنجیره از k عمل جستجوی دودویی که در یک مسیر به طول k در گراف کاتالوگ صورت می‌گیرد، در مرتبهٔ زمانی (O(log n + k log log n انجام پذیرد. کاربردها. یکی از کاربردهایی که آبشاره‌سازی جزءبه‌جزء دارد، در داده ساختارهای
که آبشاره‌سازی جزءبه‌جزء دارد، در داده ساختارهای جستجوی محدوده Range search که در هندسهٔ محاسباتی مورد استفاده قرار می‌گیرد، می‌باشد. به طور مثال، در مسئلهٔ half-plane range reporting باید تعداد n نقطهٔ ثابت را تقسیم‌بندی کرد. یکی از ساختارهایی که در این زمینه مورد استفاده قرار می‌گیرد، لایه‌های محدب convex layers می‌باشد. آبشاره‌سازی جزءبه‌جزء به این مسئله کمک می‌کند تا عملیات جستجو برای شیب‌های مربوط به هر لایه در حافظهٔ مرتبهٔ (O(n و زمان (O(log n + h صورت گیرد که در آن h اندازهٔ زیرمجموعه‌هایی از نقاط
گیرد که در آن h اندازهٔ زیرمجموعه‌هایی از نقاط است که مورد سؤال قرار می‌گیرد. با استفاده از الگوریتم Chazelle داده ساختاری که از مرتبهٔ زمانی (O(n log n ساخته می‌شود، این مسئله حل می‌شود. با توجه به این مثال، کاربرد آبشاره‌سازی جزءبه‌جزء شامل تعدادی جستجوی دودویی در یک سری خطی از لیست‌ها (سری‌های تودرتو از لایه‌های محدب) می‌باشد؛ بنابراین گراف کاتالوگ در این حالت، فقط یک مسیر ساده خواهد بود. یکی دیگر از کاربردهای آبشاره‌سازی جزءبه‌جزء در داده ساختارهای هندسی در رابطه با مکان‌یابی نقاط در نواحی یکنواخت
هندسی در رابطه با مکان‌یابی نقاط در نواحی یکنواخت monotone subdividions می‌باشد. ناحیهٔ یکنواخت، بخشی از صفحه شامل تعدادی چندضلعی است که هر خط هرکدام از چندضلعی‌ها را در حداکثر دو نقطه قطع کند. Edelsbrunne, Guibas و Stolfi در سال ۱۹۸۶ نشان دادند که برای حل این مسئله، کافیست دسته‌ای از مسیرهای به شکل چندضلعی را یافت که از چپ تا راست ناحیهٔ مورد نظر کشیده شده‌اند. سپس یک جستجوی دودویی بر روی این مسیرها باید زد تا مسیری را که در پایین‌ترین سطح قرار دارد و همچنین بالاتر از نقطهٔ مورد جستجو واقع شده‌است پیدا
بالاتر از نقطهٔ مورد جستجو واقع شده‌است پیدا کرد. این موضوع که یک نقطه بالای یک مسیر قرار دارد یا پایین آن، با جستجوی دودویی قابل بررسی است. به عبارتی باید جستجویی بر روی مختصهٔ اول از هرکدام از نقاط مسیر داشت تا مقایسه کرد که نقطهٔ مورد بررسی زیر مسیر قرار دارد یا بالای آن؛ بنابراین برای جستجوهای دودویی که صورت می‌گیرد، می‌توان از آبشاره‌سازی جزءبه‌جزء استفاده کرد و سرعت را افزایش داد. با استفاده از این روش، مرتبهٔ زمانی انجام جستجو (O(log n خواهد بود و فضای (O(n از حافظه درگیر خواهد شد. در این حالت، گراف
(O(n از حافظه درگیر خواهد شد. در این حالت، گراف کاتالوگ یک گراف درخت خواهد بود که ترتیب‌های ممکن را برای جستجوی دودویی خارجی را می‌نمایاند. کاربرد آبشاره‌سازی جزءبه‌جزء تنها در محدودهٔ هندسهٔ محاسباتی نیست. Lakshamn و Stiliadis و همچنین Buddhikot, Suri و Waldvogel از این مدل برای طراحی داده ساختارهایی در حوزهٔ فیلتر کردن بسته‌های ارتباطی در مسیریاب‌های Routers اینترنتی استفاده کرده‌اند. Gao et al نیز از آن به عنوان مدلی برای توزیع و بازیابی داده در حسگرهای شبکه‌ای استفاده کرده‌است.
مسئله پوشش بیشینه (به انگلیسی: maximum coverage problem)، یک سؤال کلاسیک در علوم رایانه و نظریه پیچیدگی محاسباتی است. این مسئله به طور گسترده در الگوریتم‌های تقریبی آموزش داده می‌شود. برای ورودی تعدادی مجموعه و یک عدد formula_1 داده می‌شود. مجموعه‌ها می‌توانند عضو مشترک داشته باشند. شما باید به تعداد حداکثر formula_1 تا از این مجموعه‌ها را انتخاب کنید به طوری که حداکثر تعداد اعضا پوشش داده شود؛ برای مثال اجتماع مجموعه‌های انتخاب شده، بیشینه تعداد اعضا را دارد. به عبارت دیگر، پوشش بیشینه (بدون وزن) نمونه:
به عبارت دیگر، پوشش بیشینه (بدون وزن) نمونه: عدد formula_1 و مجموعه‌ای از مجموعه‌ها formula_4. هدف: یافتن یک زیرمجموعهٔ formula_5 ، به طوری که formula_6 و تعداد اعضای پوشانده شده formula_7 حداکثر باشد. مسئله پوشش بیشینه یک ان‌پی سخت (به انگلیسی: NP-hard) و نمی‌تواند تحت مفروضات استاندارد با formula_8 تقریب زده شود. این نتیجه در اصل با نسبت تقریبی الگوریتم حریصانه عمومی که برای بیشینه‌سازی توابع زیرپیمان‌های با محدودیت کاردینالیتی (به انگلیسی: maximization of submodular functions with a cardinality
of submodular functions with a cardinality constraint) به کار می‌رود، مطابقت دارد. صورتبندی به شکل برنامه خطی عدد صحیح. مسئله پوشش بیشینه می‌تواند به شکل زیر در قالب برنامه‌ریزی خطی عدد صحیح (به انگلیسی: Integer Linear Program) فرمول‌بندی شود. الگوریتم حریصانه. الگوریتم حریصانه برای پوشش بیشینه، مجموعه‌ها را بر اساس یک قاعده انتخاب می‌کند: در هر مرحله، مجموعه‌ای را انتخاب کن که شامل بیشترین تعداد اعضای پوشش داده نشده باشد. می‌توان نشان داد که این الگوریتم به نسبت تقریب formula_20 می‌رسد. نتایج نشان می‌دهد
نسبت تقریب formula_20 می‌رسد. نتایج نشان می‌دهد که الگوریتم حریصانه، بهترین الگوریتم تقریب زمانی چند جمله‌ای ممکن برای پوشش بیشینه است. تعمیم‌های شناخته شده. نتایج غیرتقریبی به همهٔ تعمیم‌های مسئله پوشش بیشینه اعمال می‌شود زیرا آنها مسئله پوشش بیشینه را به عنوان یک حالت خاص دارند. حالت وزن دار. در مدل وزن دار هر عضو formula_21 وزنی برابر formula_22 دارد. هدف یافتن یک پوشش بیشینه است به طوری که بیشترین وزن را داشته باشد. حالت پایه، حالت خاصی است که همه وزن‌ها برابر formula_23 است. الگوریتم حریصانه برای پوشش
برابر formula_23 است. الگوریتم حریصانه برای پوشش بیشینه وزندار در هر مرحله مجموعه‌ای را انتخاب می‌کند که دارای بیشترین وزن اعضای پوشش داده نشده باشد. این الگوریتم به نسبت تقریب formula_20 می‌رسد. پوشش بیشینه بودجه‌ای. در حالت پوشش بیشینه بودجه‌ای (به انگلیسی: Budgeted maximum coverage)، نه تنها هر عضو formula_21 وزنی برابر formula_22 دارد، بلکه هر مجموعه formula_19 قیمتی برابر formula_40 دارد. به جای formula_1 که تعداد مجموعه‌ها در پوشش را محدود می‌کند، بودجهٔ formula_42 داده می‌شود. بودجهی formula_42 وزن
formula_42 داده می‌شود. بودجهی formula_42 وزن پوششی که می‌تواند انتخاب شود را محدود می‌کند. الگوریتم حریصانه دیگر راه حل‌هایی با تضمین کارایی ارائه نخواهد کرد. یعنی ممکن است رفتار این الگوریتم در بدترین حالت با راه حل بهینه بسیار متفاوت باشد. الگوریتم تقریب به روش زیر بدست می‌آید. ابتدا، پس از یافتن راه حلی که از الگوریتم حریصانه استفاده می‌کند، راه حل بهتر الگوریتم حریصانه و مجموعه با بیشترین وزن را بازمی‌گردانیم. این روش را، الگوریتم حریصانه اصلاح شده می‌نامیم. در مرحله دوم، با شروع از همهٔ خانواده‌های
در مرحله دوم، با شروع از همهٔ خانواده‌های ممکن مجموعه‌های اندازه‌ها از یک تا (حداقل) سه، این راه حل‌ها را با الگوریتم حریصانه اصلاح شده تقویت می‌کنیم. در مرحله سوم، بهترین راه حل تقویت شده را بازمی‌گردانیم. این الگوریتم به نسبت تقریب formula_55 می‌رسد. این بهترین نسبت تقریب ممکن است مگر formula_56. پوشش بیشینه تعمیم یافته. در تعمیم یافتهٔ پوشش بیشینه هر مجموعهٔ formula_19 قیمت formula_40 دارد، عضو formula_21 دارای وزنی متفاوت و هزینه‌ای بسته به مجموعه‌ای که آن را پوشش می‌دهد، دارد. یعنی اگر formula_21 توسط
آن را پوشش می‌دهد، دارد. یعنی اگر formula_21 توسط مجموعهٔ formula_19 پوشش داده شده باشد، وزن formula_21 برابر formula_63 و هزینهٔ آن برابر formula_64 خواهد بود. بودجه formula_65 برای هزینهٔ کل راه حل داده شده است. الگوریتم پوشش بیشینه تعمیم یافته. این الگوریتم از مفهوم باقیماندهٔ وزن/هزینه استفاده می‌کند. باقیماندهٔ وزن/هزینه در مقابل یک راه حل آزمایشی اندازه‌گیری می‌شود و این تفاوت بین وزن/هزینه و وزن/هزینه بدست آمده با یک راه حل آزمایشی است. این الگوریتم چندین مرحله دارد. اول، یافتن راه حلی که از
چندین مرحله دارد. اول، یافتن راه حلی که از الگوریتم حریصانه استفاده می‌کند. در هر تکرار الگوریتم حریصانه، راه حل آزمایشی مجموعه‌ای را که شامل بیشترین مقدار وزن اعضای باقیمانده تقسیم بر هزینهٔ این اعضا همراه با هزینه اعضای باقیمانده دارد، اضافه می‌کند. دوم، مقایسهٔ راه حل بدست آمده در قدم اول با راه حل بهینه که از تعداد کمی از مجموعه‌ها استفاده می‌کند. سوم، بازگرداندن بهترین راه حل از بین راه حل‌های بررسی شده. این الگوریتم به نسبت تقریب formula_81 می‌رسد.
الگوریتم فورچون یک الگوریتم خط جارویی برای ساختن نمودار ورونی از یک دسته نقطه در صفحه با استفاده از زمان formula_1 و حافظۀ formula_2 است. این الگوریتم اولین بار توسط استیون فورچون در سال ۱۹۸۶ در مقالۀ "یک الگوریتم خط جارویی برای نمودارهای ورونی" چاپ شد. توضیح الگوریتم. این الگوریتم هم از خط جارویی و هم از "خط ساحلی" استفاده می‌کند که هردوی این خطوط در حین پیشرفت الگوریتم روی صفحه حرکت می‌کنند. خط جارویی خط مستقیمی است که ما به صورت توافقی می‌توانیم فرض کنیم که یک خط عمودی است و از چپ به راست صفحه حرکت
کنیم که یک خط عمودی است و از چپ به راست صفحه حرکت می‌کند. در هر لحظه در طی الگوریتم نقاط ورودی سمت چپ خط جارویی با نمودار ورونی یکپارچه خواهند شد درحالی که نقاط سمت راست خط هنوز در نظر گرفته نشده‌اند. خط ساحلی یک خط نیست، بلکه یک منحنی مرکب در سمت چپ خط جارویی است که از تکه‌های سهمیها تشکیل شده است؛ این خط صفحه را به گونه‌ای تقسیم می‌کند که در آن نمودار ورونی، بدون توجه به وجود نقاط ممکن در سمت راست خط جارویی، از بقیۀ صفحه قابل تشخیص است. برای هر نقطه در سمت چپ خط جارویی، میتوان یک سهمی از نقاط هم‌فاصله از
چپ خط جارویی، میتوان یک سهمی از نقاط هم‌فاصله از آن نقطه و خط جارویی تعریف کرد. خط ساحلی مرز مجموعۀ این سهمی‌ها است. هر چه خط جارویی پیشروی می‌کند رئوس خط ساحلی، که محل تلاقی دو سهمی است، یال‌های نمودار ورونی را رسم می‌کنند. خط ساحلی طوری پیشرفت می‌کند که رأس هر سهمی دقیقأ در وسط نقاط اولیۀ خط جارویی و جایگاه جدید خط جارویی قرار بگیرد. این الگوریتم از داده ساختارها استفاده می‌کند: یک درخت جستجوی دودویی که ساختار ترکیبی خط ساحلی را توصیف می‌کند و یک صف اولویت‌دار که رخدادهای بالقوۀ بعدی را که می‌توانند
که رخدادهای بالقوۀ بعدی را که می‌توانند ساختار خط ساحلی را تغییر دهند لیست می‌کند. این رخدادها شامل اضافه کردن یک سهمی دیگر به خط ساحلی هستند (وقتی که خط جارویی از نقطۀ ورودی دیگری عبور می‌کند) و برداشتن منحنی از خط ساحلی (وقتی که خط جارویی با یک دایرۀ عبورکننده از سه نقطه، که سهمی‌هایشان بخش‌های متوالی خط ساحلی را تشکیل می‌دهند، مماس می‌شود). هر رخداد می‌تواند توسط محور xهای خط جارویی در محل وقوع رخداد، اولویت‌بندی شود. الگوریتم از برداشتن مکرر رخداد بعدی از صف اولویت‌دار، یافتن تغییراتی که آن رخداد در خط
صف اولویت‌دار، یافتن تغییراتی که آن رخداد در خط ساحلی ایجاد می‌کند و بهنگام‌سازی داده ساختارها، تشکیل می‌شود. از آنجا که formula_2 رخداد وجود دارند تا پردازش شوند (که هرکدام با برخی ویژگی‌های دیاگرام ورونی مرتبط هستند) و زمان formula_4 برای پردازش یک رخداد (که هرکدام شامل تعداد ثابتی از اعمال درخت جستجوی دودویی و صف اولویت‌دار هستند) زمان کلی الگوریتم formula_1 است. شبه‌کد. شبه‌کد توضیحات الگوریتم. let formula_6 be the transformation formula_7, where formula_8 is the Euclidean distance between formula_9
is the Euclidean distance between formula_9 and the nearest site let formula_10 be the "beach line" let formula_11 be the region covered by site formula_12. let formula_13 be the boundary ray between sites formula_12 and formula_15. let formula_16 be the sites with minimal formula_17-coordinate, ordered by formula_18-coordinate formula_19 create initial vertical boundary rays formula_20 formula_21 while not IsEmpty(formula_22) do formula_12 ← DeleteMin(formula_22) case formula_12 of formula_12 is a site in
case formula_12 of formula_12 is a site in formula_27: find the occurrence of a region formula_28 in formula_10 containing formula_12, bracketed by formula_31 on the left and formula_32 on the right create new boundary rays formula_33 and formula_34 with bases formula_12 replace formula_28 with formula_37 in formula_10 delete from formula_22 any intersection between formula_31 and formula_32 insert into formula_22 any intersection between formula_31 and formula_33 insert into formula_22 any intersection
insert into formula_22 any intersection between formula_34 and formula_32 formula_12 is a Voronoi vertex in formula_27: let formula_12 be the intersection of formula_51 on the left and formula_52 on the right let formula_53 be the left neighbor of formula_51 and let formula_55 be the right neighbor of formula_52 in formula_10 create a new boundary ray formula_58 if formula_59, or create formula_60 if formula_12 is right of the higher of formula_15 and formula_63, otherwise create formula_64 replace
formula_63, otherwise create formula_64 replace formula_65 with newly created formula_32 in formula_10 delete from formula_22 any intersection between formula_53 and formula_51 delete from formula_22 any intersection between formula_52 and formula_55 insert into formula_22 any intersection between formula_53 and formula_32 insert into formula_22 any intersection between formula_32 and formula_55 record formula_12 as the summit of formula_51 and formula_52 and the base of formula_32 output the boundary
and the base of formula_32 output the boundary segments formula_51 and formula_52 endcase endwhile output the remaining boundary rays in formula_10 بخش‌ها و دیسک‌های وزن‌دار. همان‌طور که فورچون در توضیح داده است، یک نوع الگوریتم توسعه‌یافتۀ خط جارویی می‌تواند برای ساخت نمودار ورونی وزن‌دارافزایشی استفاده شود، که در آن فاصلۀ هر بخش با وزن آن تعیین می‌شود؛ که این می‌تواند برابر با نمودار ورونی مجموعه‌ای از دیسک‌های هم‌مرکز بخش‌ها و به شعاع وزن آن‌ها باشد. زمانی که از نمودار ورونی برای ساخت treemapها استفاده
که از نمودار ورونی برای ساخت treemapها استفاده می‌شود، می‌توان از بخش‌های وزن‌دار برای کنترل مکان‌های سلولی ورونی استفاده کرد. در یک دیاگرام ورونی وزن‌دار افزایشی، نیم‌ساز بین بخش‌ها به‌طور عمومی یک هذلولی است در حالی که در نمودارهای ورونی غیروزن‌دار و نمودار پاور دیسک‌ها نیم‌ساز یک خط مستقیم است.
در علوم کامپیوتر، درخت بازه‌ای یک داده ساختار مرتب درختی برای نگهداری و ذخیره‌سازی بازه‌ها می‌باشد. می‌توان گفت این از درخت این امکان را فراهم می‌سازد تا همۀ بازه‌هایی را که با یک بازه یا نقطۀ خاص اشتراک دارند پیدا کنیم. درخت بازه‌ای به‌طور معمول برای پنجره دار کردن پرس و جوها به کار می‌رود. برای مثال، یافتن تمام راه‌های موجود بر روی یک نقشۀ کامپیوتری درون یک دید مستطیلی یا یافتن تمام نقاط قابل رویت درون یک چشم انداز سه بعدی. یک ساختار داده مشابه این داده ساختار، از درخت بخشی است. راه حل بدیهی این است که
ساختار، از درخت بخشی است. راه حل بدیهی این است که تمام بازه‌ها را ملاقات کرده و امتحان کنیم که آیا با نقطه یا بازه داده شده اشتراک دارند یا نه، که به theta(n) زمان نیاز دارد. (که n همان تعداد بازه‌های موجود در مجموعه است) از آنجایی که یک پرسش ممکن است تمام بازه‌ها را برگرداند، به‌طور مثال، اگر پرسش مورد نظر یک بازۀ بزرگ باشد که با همۀ بازه‌های موجود در مجموعه اشتراک داشته باشد، این به صورت مجانبی بهینه است؛ اگر که ما از الگوریتم‌های حساس به خروجی که در آن‌ها زمان اجرا بر اساس m (که همان تعداد بازه‌های
آن‌ها زمان اجرا بر اساس m (که همان تعداد بازه‌های تولید شده توسط پرس و جوست) بیان می‌شود استفاده کنیم می‌توانیم این فرایند را بهبود ببخشیم. درخت‌های بازه‌ای پویا هستند. آن‌ها اجازه درج و حذف بازه‌ها را می‌دهند. آن‌ها پرس و جو را در زمان O(logn) انجام می‌دهند. این در حالی است که زمان پیش پردازش برای ساخت این داده ساختار از O(nlogn) است (ولی فضای مصرف شده از O(n) است). اگر انتهای بازه‌ها در محدودۀ کوچکی قرار داشته باشند (مثلاً محدوده [1...,O(n)])، داده ساختارهای سریع‌تری با زمان پیش پردازش O(n) و زمان پرس و
سریع‌تری با زمان پیش پردازش O(n) و زمان پرس و جوی O(1+m) وجود دارند که m بازه (شامل یک نقطه پرس و جو) را گزارش می‌کنند. عملکرد ساده. در یک حالت ساده، بازه‌ها با هم هیچ گونه اشتراکی ندارند و می‌توانند در یک درخت جستجوی دودویی ساده درج شده و در زمان O(logn) پرس و جو شوند. این در حالی است که با وجود اشتراک‌های دلخواه میان بازه‌ها، به هیچ عنوان امکان مقایسه دو بازه برای درج در درخت وجود ندارد. زیرا مرتب سازی‌ها بر حسب نقاط شروع یا پایان ممکن است متفاوت باشد. یک عملکرد ساده این خواهد بود که دو درخت موازی
یک عملکرد ساده این خواهد بود که دو درخت موازی بسازیم. یکی مرتب شده بر حسب نقاط شروع و دیگری مرتب شده بر حسب نقاط انتهای هر بازه. این کار اجازۀ رها کردن نصف درخت را در O(logn) می‌دهد ولی نتیجه‌ها باید ادغام شوند که به O(n) زمان نیاز دارد. این راه حل به ما پرس و جوهایی در زمان O(n) = O(n + logn) می‌دهد که بهتر از راه حل بدیهی نیست. درخت بازه‌ای مرکزی. پرس و جوها به زمان o(m + log(n)) نیاز دارند که در آن n تعداد کل بازه‌ها و m تعداد نتایج گزارش شده‌است. ساخت داده ساختار نیز به o(nlogn) زمان و O(n) فضا نیاز
داده ساختار نیز به o(nlogn) زمان و O(n) فضا نیاز دارد. ساختار. به ما یک مجموعه n تایی از بازه‌ها در خط اعداد داده می‌شود و ما می خواهیم یک داده ساختار بسازیم که بتواند به صورت مؤثری همه بازه‌هایی را که با یک نقطه یا بازه اشتراک دارند بازیابی کند. ما با مشخص کردن محدوده کل بازه‌ها و تقسیم کردن آن در x_center (در عمل، x_center باید مشخص شود تا درخت را نسبتاً متعادل نگه داریم) شروع می کنیم. این فرایند سه مجموعه از بازه‌ها را تولید می‌کند: 1. بازه‌هایی که کاملاً در سمت چپ x_center قرار می‌گیرند که ما آن‌ها را
در سمت چپ x_center قرار می‌گیرند که ما آن‌ها را S_left نام‌گذاری می‌کنیم. 2. بازه‌هایی که کاملاً در سمت راست x_center قرار می‌گیرند که ما آن‌ها را S_right نام‌گذاری می‌کنیم. 3. آنهایی که با x_center اشتراک دارند که ما آن‌ها را S_center می‌نامیم. بازه‌های S_left و S_rightنیز به طریق مشابه به صورت بازگشتی تقسیم می‌شوند تا زمانی که هیچ بازه‌ای باقی نماند. بازه‌هایی از S_center که با نقطۀ مرکزی تلاقی دارند در یک داده ساختار جداگانه مرتب می‌شوند که به گره‌های درخت بازه‌ای پیوند داده شده‌است. این داده ساختار از
بازه‌ای پیوند داده شده‌است. این داده ساختار از دو لیست تشکیل شده‌است: یکی شامل همه بازه‌هایی که بر حسب نقاط شروع‌شان مرتب شده‌اند و دیگری شامل همۀ بازه‌هایی که برحسب نقاط پایانشان مرتب شده‌اند. نتیجه، یک درخت ثالث است که هر گره شامل موارد زیر است: 1. یک نقطه مرکزی 2. یک اشاره‌گر به یک گره دیگر شامل همۀ بازه‌هایی که به‌طور کامل در سمت چپ نقطۀ مرکزی قرار می‌گیرند. 3. یک اشاره‌گر به یک گره دیگر شامل همۀ بازه‌هایی که به‌طور کامل در سمت راست نقطۀ مرکزی قرار می‌گیرند. 4. همۀ بازه‌های شامل نقطۀ مرکزی که بر اساس
4. همۀ بازه‌های شامل نقطۀ مرکزی که بر اساس نقطۀ شروع‌شان مرتب شده‌اند. 5. همۀ بازه‌های شامل نقطۀ مرکزی که بر اساس نقطۀ پایان‌شان مرتب شده‌اند. اشتراکی. به ما داده ساختار ساخته‌شده در بالا داده می‌شود. ما پرس و جوهایی را شامل بازه‌ها یا نقاط داده شده دریافت می‌کنیم و تمام بازه‌های موجود در بازه‌های اصلی و تمام بازه‌های موجود در مجموعۀ اصلی را که با این ورودی اشتراک دارند برمی‌گردانیم. با یک بازه. اول می‌توانیم حالتی را که یک بازه R به عنوان ورودی داده می‌شود به حالت ساده‌تر که در آن یک نقطه به عنوان ورودی
به حالت ساده‌تر که در آن یک نقطه به عنوان ورودی داده شده‌است کاهش دهیم. در ابتدا همۀ بازه‌هایی را که نقطۀ شروع یا پایان‌شان در درون بازۀ ورودی R قرار دارد، با استفاده از یک درخت جداگانه می‌یابیم. در حالت یک بعدی می‌توانیم از یک درخت ساده شامل همۀ نقاط شروع و پایان در مجموعۀ بازه‌ها استفاده کنیم که هرکدام شامل یک نشانه‌گر به بازۀ مربوط به آن است. یک جستجوی دودویی در زمان O(logn) برای شروع و پایان R، کمینه و بیشینۀ نقاطی را که باید در نظر گرفته شوند مشخص می‌کند. هر نقطه با این محدوده به تمام بازه‌هایی که با
هر نقطه با این محدوده به تمام بازه‌هایی که با محدودۀ مورد نظر ما تلاقی دارند ارجاع می‌دهد و به لیست نتیجه اضافه می‌شود. باید توجه شود که از ایجاد تکرار جلوگیری شود، زیرا ممکن است هم شروع و هم پایان یک بازه با R باشد. این کار را می‌توان با استفاده از یک پرچم دودویی بر روی هر بازه برای مشخص کردن اینکه این بازه به مجموعۀ نتیجه اضافه شده‌است یا نه، انجام داد. تنها بازه‌هایی که هنوز در نظر گرفته نشده‌اند بازه‌هایی هستند که با R تلاقی دارند ولی نقاط پایان‌شان درون R نیست، به عبارت دیگر، بازه‌هایی که آن را در بر
R نیست، به عبارت دیگر، بازه‌هایی که آن را در بر می‌گیرند. برای پیدا کردن آن‌ها ما هر نقطه در درون را در نظر می‌گیریم و از الگوریتم زیر استفاده می‌کنیم تا همۀ بازه‌هایی را که با آن نقطه اشتراک دارند بیابیم. (دوباره مواظب باشید که تکرارها را حذف کنید) با یک نقطه. این فرایند در واقع یافتن همه بازه‌های موجود در درخت است که با یک نقطه x داده شده اشتراک دارند. درخت به همان شیوه پیمایش یک درخت مرسوم دودویی پیمایش می‌شود، ولی با کارآیی بیشتر برای بازه‌هایی که با نقطۀ مرکزی در هر گره تلاقی دارند. برای هر گره درخت،
مرکزی در هر گره تلاقی دارند. برای هر گره درخت، x با x_center مقایسه می‌شود، یعنی همان نقطۀ میانی که برای ساخت گره در بالا استفاده شده‌است. اگر x از x_center کوچک‌تر باشد، چپ‌ترین مجموعه از بازه‌ها S_left در نظر گرفته می‌شود. اگر x از x_center بزرگ‌تر باشد، راست‌ترین مجموعه از بازه‌ها S_right در نظر گرفته می‌شود. همین طور که هر گره پردازش می‌شود، وقتی ما درخت را از ریشه به یک برگ می‌پیماییم، محدوده‌های موجود در S_center آن پردازش می‌شوند. اگر x از x_center کوچک‌تر باشد، ما می‌دانیم که تمام بازه‌های موجود
کوچک‌تر باشد، ما می‌دانیم که تمام بازه‌های موجود s_center بعد x تمام می‌شوند یا اینکه اصلاً با x_center برخورد ندارند. بنابراین ما تنها به یافتن بازه‌هایی از s_centerنیاز داریم که قبل از x شروع می‌شود. ما توانیم در مورد لیست‌های s_center که تاکنون ساخته شده‌اند بحث کنیم. از آنجایی که ما در این سناریو تنها به شروع بازه‌ها اهمیت می‌دهیم، می‌توانیم در مورد لیست مرتب شده بر اساس شروع بازه‌ها بحث کنیم. فرض کنید ما در لیست نزدیک‌ترین عددی که بزرگ‌تر از x نیست را بیابیم. تمام محدوده‌ها از شروع لیست تا آن نقطه
را بیابیم. تمام محدوده‌ها از شروع لیست تا آن نقطه یافته شده با x تلاقی دارند، چون قبل از x شروع شده و بعد از x تمام می‌شوند. (همان طور که می‌دانیم به علت این است که با x_center که بزرگ‌تر از x است تلاقی دارند) بنابراین می‌توانیم شروع به شماره‌گذاری بازه‌های موجود در لیست کنیم تا زمانی که مقدار نقطه پایانی از x بیشتر شود. همچنین اگر x از x_center بزرگ‌تر باشد، ما می‌دانیم که همۀ بازه‌های موجود در s_center باید قبل از x شروع شوند پس ما بازه‌هایی را که بعد از x پایان می‌یابند به وسیلۀ لیستی که بر اساس پایان
x پایان می‌یابند به وسیلۀ لیستی که بر اساس پایان بازه‌ها مرتب شده‌است می‌یابیم. اگر x دقیقاً منطبق بر x_center باشد، تمام فواصل را می‌توان بدون پردازش بیشتر به نتایج اضافه کرد و پیمایش درخت می‌تواند متوقف شود. ابعاد بالاتر. ساختمان داده درخت را می‌توان با پرس و جو و زمان ساخت یکسان و فضای O(nlogn) به ابعاد بالاتر n تعمیم داد. اول یک درخت محدوده در ابعاد N ساخته شده‌است که اجازه بازیابی کارآمد از تمام فواصل با شروع و پایان نقاط در داخل منطقۀ پرس و جو Rرا می‌دهد. هنگامی که تمام بازه‌های مربوطه یافت شدند،
می‌دهد. هنگامی که تمام بازه‌های مربوطه یافت شدند، تنها چیزی که باقی می‌ماند آن بازه‌هایی است که ناحیه را بعضی ابعاد در بر می‌گیرند. برای پیدا کردن این همپوشانی‌ها، N درخت بازه‌ای به وجود می‌آیند و یک محور متقاطع با R برای هرکدام پرس و جو می‌شود. برای مثال، در دو بعد، پایین مربع R (یا هر خط افقی متقاطع با R) در برابر درخت بازه‌ای ساخته شده برای محور افقی پرس و جو می‌شود. به همین ترتیب سمت چپی (یا هر خط عمودی متقاطع با R) در برابر درخت بازه‌ای ساخته شده بر محور عمودی پرس و جو می‌شود. هر درخت بازه‌ای به یک
محور عمودی پرس و جو می‌شود. هر درخت بازه‌ای به یک چیز اضافه در ابعاد بالاتر نیز نیاز دارد. در هر گره که ما آن را در درخت پیمایش می‌کنیم برای پیدا کردن تلاقی‌ها x با s_center مقایسه می‌شود. به جای دو لیست مرتب شده از بازه‌ها که در حالت یک بعدی مورد استفاده قرار می‌گرفت یک درخت محدوده ساخته می‌شود. این امکان بازیابی کارآمد تمام بازه‌های موجود در s_center را (که با ناحیه R تلاقی دارند) فراهم می‌سازد. حذف. اگر پس از حذف یک بازه از درخت، گره شامل آن بازه شامل هیچ بازه دیگری نباشد، آن گره ممکن است از درخت حذف
هیچ بازه دیگری نباشد، آن گره ممکن است از درخت حذف شود. این فرایند پیچیده‌تر از عملیات حذف در یک درخت معمولی دودویی است. یک بازه ممکن است با مرکز چند گره در درخت تلاقی داشته باشد. از آنجایی که هر گره بازه‌هایی را که با آن تلاقی دارند ذخیره می‌کند، به همراه تمام بازه‌های به‌طور کامل سمت چپ نقطۀ مرکز آن در زیر درخت سمت چپ و به‌طور مشابه برای زیر درخت راست. این نتیجه می‌دهد که هر بازه از بین بازه‌هایی که با مرکز آن‌ها تلاقی دارد در نزدیک‌ترین گره به ریشه ذخیره می‌شود. عملیات حذف عادی در یک درخت دودویی (برای
می‌شود. عملیات حذف عادی در یک درخت دودویی (برای حالتی که گره در حال حذف شدن دارای دو فرزند باشد) شامل ارتقاء یک گره دورتر از ریشه به جایگاه گره در حال حذف است (معمولاً چپ‌ترین درخت زیردرخت راست یا راست‌ترین درخت زیر درخت چپ). به عنوان یک نتیجه این ارتقاء، بعضی از گره‌هایی که بالای گره ارتقاء یافته بودند به نوادگان آن تبدیل خواهند شد. لازم است که این گره‌ها را برای بازه‌هایی که با گره ارتقاء یافته تلاقی دارند نیز جستجو کنیم و آن بازه‌ها را به داخل گره‌های ارتقاء یافته منتقل کنیم. در نتیجه این ممکن است باعث
یافته منتقل کنیم. در نتیجه این ممکن است باعث ایجاد گره‌های خالی جدیدی شود که دوباره طبق همان الگوریتم باید حذف شوند. ایجاد تعادل. همان مسائلی که بر روی عملیات حذف تأثیر می‌گذارند، بر روی عملیات چرخش نیز تأثیر می‌گذارند. چرخش باید ثابتی را که بازه‌ها ذخیره شده‌اند تا حد امکان نزدیک به ریشه نگه دارد. درخت افزوده. هم درج و هم حذف از O(logn) زمان می‌برند، که n همان تعداد کل بازه‌هاست. از یک درخت ساده مرتب استفاده کنید. برای مثال یک درخت جستجوی دودویی یا یک درخت خود-متعادل جستجوی دودویی، که درخت بر اساس نقاط
خود-متعادل جستجوی دودویی، که درخت بر اساس نقاط پایین بازه‌ها مرتب شده‌است و یک توضیح اضافه به هر گره اضافه شده‌است که ماکزیمم نقاط بالای بازه‌ها را در زیر درخت‌های آن نگه می‌دارد. به دست آوردن این صفت در طی تنها O(h) مرحله هنگام حذف یا درج یک گره کار ساده‌ای است، که h همان ارتفاع گره درج یا حذف شده به وسیله به روز رسانی همۀ اجداد گره از پایین به بالا در درخت می‌باشد. به علاوه، چرخش‌های درخت که در حذف و درج مورد استفاده قرار می‌گرفت، ممکن است نیاز به به روز رسانی قسمت بالای گره‌های مورد تأثیر داشته باشد. در