شجرة المقاطع: الإنشاء والاستعلام
إيجاد أصغر قيمة أو أكبر قيمة أو مجموع نطاق في log n
شجرة المقاطع: الإنشاء والاستعلام درس مجاني في Coding Interview Prep على CoddyKit. هذا هو الدرس 3 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Coding Interview Prep، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
ما بعد شجرة Fenwick
تتألق شجرة Fenwick مع المجاميع، لكن شجرة المقاطع تتعامل مع الحد الأدنى والحد الأقصى والقاسم المشترك الأكبر وغير ذلك. إنها أداة العمل المرنة لاستعلامات النطاق.
شجرة فوق النطاقات
تمتلك كل عقدة نطاقًا من المصفوفة. يغطي الجذر كل شيء، ويقسّمه الأبناء إلى نصفين حتى تحتوي الأوراق على عناصر مفردة.
تخزين مدعوم بمصفوفة
نخزّن الشجرة في مصفوفة مسطّحة بحجم 2n أو 4n. العقدة 1 هي الجذر؛ ويقع ابنا العقدة i عند 2i و2i+1.
seg = [0] * (2 * n)تحتوي الأوراق على البيانات
في الصيغة التكرارية، تعيش القيم الأصلية في النصف الثاني من المصفوفة، عند الفهارس من n إلى 2n-1.
for i in range(n):
seg[n + i] = a[i]البناء من الأسفل إلى الأعلى
كل عقدة داخلية هي ناتج combine لابنيها. املأ العقد من n-1 نزولًا إلى 1، وستصبح الشجرة بأكملها جاهزة.
for i in range(n - 1, 0, -1):
seg[i] = seg[2*i] + seg[2*i+1]عملية الدمج
تحدّد دالة combine بنية الشجرة. استخدم الجمع للمجاميع، أو min للقيم الدنيا، أو max للقيم القصوى. بدّلها لتغيير الاستعلام.
def combine(x, y):
return min(x, y)تحديث نقطة ثم الصعود
لتغيير قيمة واحدة، اضبط الورقة واصعد إلى الجذر، مع إعادة حساب كل أب من ابنيه على طول الطريق.
i += n
seg[i] = value
while i > 1:
i //= 2
seg[i] = combine(seg[2*i], seg[2*i+1])الاستعلام عن نطاق نصف مفتوح
تفحص استعلامات النطاق الطرفين، وتضمّن العقد الحدّية في الإجابة. والفترة نصف مفتوحة، إذ تغطي من l حتى ما قبل r.
حلقة الاستعلام التكرارية
حرّك l وr باتجاه بعضهما. عندما يكون الفهرس حدًا فرديًا، أدرج تلك العقدة قبل تحريك المؤشر.
while l < r:
if l & 1: res = combine(res, seg[l]); l += 1
if r & 1: r -= 1; res = combine(res, seg[r])
l //= 2; r //= 2لوغاريتمي من الطرفين
يستغرق البناء O(n)، بينما يستغرق كل تحديث واستعلام O(log n). وهذا التوازن هو ما يجعل أشجار المقاطع متعددة الاستخدامات.
انتبه إلى العنصر المحايد
ابدأ نتيجتك من العنصر المحايد للعملية: 0 للجمع، واللانهاية للقيمة الدنيا، وسالب اللانهاية للقيمة القصوى. تؤدي البداية الخاطئة إلى إجابات خاطئة.
res = float('inf')اختبار سريع
أين توجد البيانات الخام في الشجرة التكرارية؟
مراجعة: نطاقات مرنة
أنشأت شجرة مقاطع: أوراقها في النصف الثاني، وآباؤها نواتج عمليات combine، مع تحديثات واستعلامات في O(log n) للمجموع أو الحد الأدنى أو الحد الأقصى. 🌳
الأسئلة الشائعة
هل درس «شجرة المقاطع: الإنشاء والاستعلام» مجاني؟
نعم — نص درس «شجرة المقاطع: الإنشاء والاستعلام» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Coding Interview Prep، انتقل إلى CoddyKit PRO. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
ماذا ستتعلم في «شجرة المقاطع: الإنشاء والاستعلام»؟
إيجاد أصغر قيمة أو أكبر قيمة أو مجموع نطاق في log n تتمرن على Coding Interview Prep مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Coding Interview Prep؟
لا تُشترط خبرة سابقة. Coding Interview Prep على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 3 من أصل 4.
كم من الوقت يستغرق درس «شجرة المقاطع: الإنشاء والاستعلام»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Coding Interview Prep هذا؟
نعم. كل درس في Coding Interview Prep يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- شجرة Fenwick للمجاميع السابقة
- الانقلابات باستخدام BIT
- شجرة المقاطع: الإنشاء والاستعلام
- الانتشار الكسول لتحديثات النطاق