محاسبه مساحت مستطیل های موازی محورهای مختصات با segment tree

مساله به klee's rectangle problem معروف است و راه حل توسط Bentley ارائه شده است.

یک sweep عمودی انجام می دهیم و هر بار اجتماع بازه هایی که داخل مستطیل ها هستند (xشان) را حساب می کنیم. (با segment tree)

این را در اختلاف y این مرحله sweep با مرحله ی قبل ضرب می کنیم و جمع اینها در کل sweep میشه جواب.