الانقلابات باستخدام BIT
عدّ الأزواج الخارجة عن الترتيب بكفاءة
الانقلابات باستخدام BIT درس مجاني في Coding Interview Prep على CoddyKit. هذا هو الدرس 2 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Coding Interview Prep، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
ما هو الانقلاب
الانقلاب هو زوج i < j حيث a[i] > a[j]. إنه زوج واحد خارج الترتيب، ويقيس عدّه مدى عدم ترتيب المصفوفة.
لماذا تهم الانقلابات
يساوي عدد الانقلابات عدد عمليات التبديل التي ستجريها bubble sort. وتخفيها مسائل المسابقات داخل أسئلة الترتيب والفوضى.
العدّ الساذج بطيء جدًا
يستغرق فحص كل زوج O(n^2). وعندما تكون n في حدود 100000، فهذا يعني عشرة مليارات عملية فحص، وهو أبعد بكثير من الحد الزمني. نحتاج إلى حل أذكى. 🐢
فكرة BIT
امسح المصفوفة من اليسار إلى اليمين واسأل: كم عنصرًا سابقًا أكبر من العنصر الحالي؟ تجيب شجرة Fenwick عن ذلك أثناء المسح.
العدّ حسب التكرار
تخزّن BIT جدول تكرارات للقيم. ويسجّل update(v, 1) أن القيمة v ظهرت حتى الآن أثناء المسح.
update(v, 1)الأكبر يعني لاحقة
تساوي القيم السابقة الأكبر من v عدد العناصر التي ظهرت مطروحًا منه عدد العناصر حتى v. أي إنها i ناقص query(v) عند العنصر ذي الفهرس i.
inv += i - query(v)ضغط الإحداثيات
إذا كانت القيم كبيرة أو سالبة، فحوّلها أولًا إلى رتب من 1 إلى n. يحافظ هذا الضغط على صغر حجم BIT من دون تغيير أي ترتيب.
rank = {v: i for i, v in enumerate(sorted(set(a)), 1)}المسح الكامل
كرّر على المصفوفة، وأضف عدد القيم الأكبر إلى المجموع، ثم أدرج القيمة الحالية. يمثّل المجموع الجاري عدد الانقلابات.
for i, v in enumerate(a):
inv += i - query(rank[v])
update(rank[v], 1)يعمل في n log n
يؤدي كل عنصر استعلامًا وتحديثًا واحدًا، وكلاهما في O(log n). وينتهي العدّ بالكامل في زمن O(n log n). 🚀
الفرز بالدمج قريب له
يعدّ الفرز بالدمج الانقلابات أيضًا في O(n log n) أثناء خطوة الدمج. وغالبًا ما تكون نسخة BIT أقصر في الكتابة تحت ضغط الوقت.
انتبه إلى تجاوز سعة العدّ
قد يصل عدد الانقلابات إلى نحو n تربيع مقسومًا على اثنين، وهو عدد هائل. أعداد Python غير محدودة السعة، لكنك ستحتاج في اللغات الأخرى إلى نوع 64-bit.
اختبار سريع
اختبر مدى فهمك لتكلفة المسح.
مراجعة: عدّ الفوضى
عددت الانقلابات في O(n log n) عبر المسح من اليسار إلى اليمين وسؤال BIT عن عدد القيم الأكبر التي ظهرت سابقًا. اضغط القيم عند الحاجة. ✅
الأسئلة الشائعة
هل درس «الانقلابات باستخدام BIT» مجاني؟
نعم — نص درس «الانقلابات باستخدام BIT» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Coding Interview Prep، انتقل إلى CoddyKit PRO. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
ماذا ستتعلم في «الانقلابات باستخدام BIT»؟
عدّ الأزواج الخارجة عن الترتيب بكفاءة تتمرن على Coding Interview Prep مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Coding Interview Prep؟
لا تُشترط خبرة سابقة. Coding Interview Prep على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 2 من أصل 4.
كم من الوقت يستغرق درس «الانقلابات باستخدام BIT»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Coding Interview Prep هذا؟
نعم. كل درس في Coding Interview Prep يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- شجرة Fenwick للمجاميع السابقة
- الانقلابات باستخدام BIT
- شجرة المقاطع: الإنشاء والاستعلام
- الانتشار الكسول لتحديثات النطاق