شجرة القطاعات

ليكن I مجموعة من الفترات، أو القطع المستقيمة. ولتكن p₁ , p₂ _, ..., _pₘ قائمة بنقاط نهاية الفترات المختلفة، مرتبة من اليسار إلى اليمين. لننظر إلى تقسيم خط الأعداد الحقيقية الناتج عن هذه النقاط. تُسمى مناطق هذا التقسيم _{بالفترات} الأولية . وبالتالي، فإن الفترات الأولية هي، من اليسار إلى اليمين:

${\displaystyle (-\infty ,p_{1}),[p_{1},p_{1}],(p_{1},p_{2}),[p_{2},p_{2}],\dots ,(p_{m-1},p_{m}),[p_{m},p_{m}],(p_{m},+\infty )}$

أي أن قائمة الفترات الأولية تتكون من فترات مفتوحة بين نقطتي نهاية متتاليتين pᵢ و pᵢ ₊ 1 _{، بالتناوب} مع فترات مغلقة تتكون من نقطة نهاية واحدة. تُعامل النقاط المفردة نفسها كفترات لأن إجابة الاستعلام ليست بالضرورة هي نفسها داخل الفترة الأولية ونقطتي نهايتها. ^{[ 2 ]}

بالنظر إلى مجموعة I من الفترات أو القطع، فإن شجرة القطع T لـ I يتم تنظيمها على النحو التالي:

• T عبارة عن شجرة ثنائية .
• تتوافق أوراقها مع الفترات الأولية الناتجة عن نقاط النهاية في I ، بطريقة مرتبة: تتوافق الورقة الموجودة في أقصى اليسار مع الفترة الموجودة في أقصى اليسار، وهكذا. يُرمز إلى الفترة الأولية المقابلة للورقة v بالرمز Int( v ).
• تُقابل العقد الداخلية للشجرة T فتراتٍ هي اتحاد فتراتٍ أولية : الفترة Int( N ) المقابلة للعقدة N هي اتحاد الفترات المقابلة لأوراق الشجرة التي جذرها N. وهذا يعني أن Int( N ) هي اتحاد فترات فرعيها.
• تخزن كل عقدة أو ورقة v في T الفترة Int( v ) ومجموعة من الفترات، ضمن بنية بيانات معينة. تحتوي هذه المجموعة الفرعية الأساسية للعقدة v على الفترات [ x , x ′ ] من I بحيث تحتوي [ x , x ′ ] على Int( v ) ولا تحتوي على Int(parent( v )). أي أن كل عقدة في T تخزن القطع المستقيمة التي تمتد عبر فترتها، ولكنها لا تمتد عبر فترة العقدة الأب. ^{[ 3 ]}

يمكن بناء شجرة قطاعات من مجموعة القطاعات I كما يلي: أولًا، تُرتَّب نهايات الفترات في I ، ومن ثم تُستخرج الفترات الأولية. بعد ذلك، تُبنى شجرة ثنائية متوازنة على الفترات الأولية، ويُحدَّد لكل عقدة v الفترة Int( v ) التي تُمثِّلها. يبقى حساب المجموعات الجزئية الأساسية للعقد. ولتحقيق ذلك، تُدرَج الفترات في I واحدة تلو الأخرى في شجرة القطاعات. يمكن إدراج فترة X = [ x , x ′ ] في شجرة فرعية جذرها T ، باستخدام الإجراء التالي: ^{[ 4 ]}

• إذا كان Int( T ) موجودًا في X، فقم بتخزين X في T ، ثم أنهِ العملية.
• آخر:
  • إذا تقاطع X مع الفترة الخاصة بالفرع الأيسر لـ T ، فقم بإدخال X في ذلك الفرع، بشكل متكرر.
  • إذا تقاطع X مع فترة الابن الأيمن لـ T ، فقم بإدخال X في ذلك الابن، بشكل متكرر.

تستغرق عملية البناء الكاملة O ( n log n ) من الوقت، حيث n هو عدد الأجزاء في I.

يستقبل الاستعلام عن شجرة القطاعات نقطة q _x (يجب أن تكون واحدة من أوراق الشجرة)، ويسترجع قائمة بجميع القطاعات المخزنة التي تحتوي على النقطة q _x .

بصورة رسمية؛ بالنظر إلى عقدة (شجرة فرعية) v ونقطة استعلام q _x ، يمكن إجراء الاستعلام باستخدام الخوارزمية التالية:

1. قم بالإبلاغ عن جميع الفترات في I ( v ) .
2. إذا لم تكن v ورقة:
   • إذا كان q _x ينتمي إلى مجموعة الأعداد الصحيحة (الابن الأيسر لـ v )، فإن
     • قم بإجراء استعلام في الفرع الأيسر من v .
   • إذا كان q _x ينتمي إلى Int(الابن الأيمن لـ v ) فإن
     • قم بإجراء استعلام في الفرع الأيمن من v .

في شجرة القطاعات التي تحتوي على n فترات، يمكن الإبلاغ عن تلك التي تحتوي على نقطة استعلام معينة في وقت O (log n + k )، حيث k هو عدد الفترات المبلغ عنها.

تستخدم شجرة القطاعات T على مجموعة I من n فترات مساحة تخزين O ( n log n ).

تحتوي المجموعة I على 4n + 1 فترة أولية على الأكثر . ولأن T شجرة ثنائية متوازنة تحتوي على 4n + 1 ورقة على الأكثر ، فإن ارتفاعها هو O(log n ). وبما أن أي فترة تُخزَّن مرتين على الأكثر عند عمق معين من الشجرة، فإن إجمالي مساحة التخزين هو O ( n log n ). ^{[ 5 ]}

يمكن تعميم شجرة القطاعات لتشمل فضاءات ذات أبعاد أعلى، على شكل أشجار قطاعات متعددة المستويات. في الإصدارات ذات الأبعاد الأعلى، تخزن شجرة القطاعات مجموعة من المستطيلات (المستطيلات الفائقة) المتوازية مع المحاور، ويمكنها استرجاع المستطيلات التي تحتوي على نقطة استعلام معينة. يستخدم هذا الهيكل مساحة تخزين من رتبة O ( n log ^d n )، ويجيب على الاستعلامات في زمن قدره O (log ^d n ).

يؤدي استخدام التتالي الجزئي إلى تقليل حد وقت الاستعلام بمعامل لوغاريتمي. كما يؤدي استخدام شجرة الفترات على أعمق مستوى من الهياكل المرتبطة إلى تقليل حد التخزين بمعامل لوغاريتمي. ^{[ 6 ]}