شجرة فينويك

يتم تعريف شجرة الاستجواب بحيث يكون الأصل للعقدة${\displaystyle i}$يكون${\displaystyle i-\operatorname {lsb} (i)=i\mathbin {\&} (i-1)}$على سبيل المثال، الأصل للعدد 6 = 110 ₂ هو العدد 4 = 100 _2. العقدة الضمنية 0 هي الجذر.

كل مستوى${\displaystyle k}$تحتوي الشجرة على عقد ذات مؤشرات تتوافق مع مجاميع من${\displaystyle k}$قوى مميزة للعدد 2 (مع${\displaystyle k=0}$يمثل مجموعًا فارغًا (0). على سبيل المثال، المستوى${\displaystyle k=1}$يحتوي على عقد${\displaystyle 1=2^{0},2=2^{1},4=2^{2},...}$والمستوى${\displaystyle k=2}$يحتوي على عقد${\displaystyle 3=2^{1}+2^{0},5=2^{2}+2^{0},6=2^{2}+2^{1},...}$

العقدة${\displaystyle i}$لديه${\displaystyle \log _{2}(\operatorname {lsb} (i))}$أطفال (${\displaystyle i+1,i+2,i+4,...,i+\operatorname {lsb} (i)/2}$)، و${\displaystyle \operatorname {lsb} (i)}$إجمالي النسل. (تشمل هذه الأرقام العقد الأكبر من${\displaystyle n}$(والتي يتم حذفها ولا يتم الوصول إليها مطلقًا.)

يوضح الرسم التخطيطي أدناه بنية شجرة استعلام شجرة فينويك المكونة من 16 عقدة، بما في ذلك الجذر، بحيث تتوافق مع مصفوفة A المكونة من 15 عنصرًا:

لإيجاد المجموع البادئ${\displaystyle A[1]+\cdots +A[i]}$، اجمع القيم في${\displaystyle i}$، ووالده، ووالد والده، وهكذا حتى الجذر (ولكن ليس بما فيه). لحساب مجموع النطاق${\displaystyle A[i]+\cdots +A[j]}$اطرح المجاميع البادئة لـ${\displaystyle i-1}$و${\displaystyle j}$.

يمكن تحسين ذلك بالتوقف عند أول سلف مشترك لهم. ومن الأمثلة المتطرفة طلب مدخل واحد فقط.${\displaystyle A[j]}$في هذه الحالة، السلف المشترك لـ${\displaystyle j}$و${\displaystyle i=j-1}$يكون${\displaystyle j-\operatorname {lsb} (j)}$لذا ابدأ بـ${\displaystyle F[j]}$وبعد ذلك، طالما${\displaystyle i\neq j-\operatorname {lsb} (j)}$اطرح${\displaystyle F[i]}$وتحديث .i := i - lsb(i)

شجرة التحديث هي صورة معكوسة لشجرة الاستعلام. الأصل للعقدة${\displaystyle i}$يكون${\displaystyle i+\operatorname {lsb} (i)=(i\mathbin {|} (i-1))+1}$(حيث يرمز الرمز | إلى عملية OR الثنائية ). على سبيل المثال، العدد الأب للعدد 6 = 110 ₂ هو العدد 8 = 1000 ₂ .

هذه الشجرة المفاهيمية لا نهائية، ولكن فقط الجزء الذي يحتوي على فهارس تصل إلى${\displaystyle n}$يتم تخزينها أو استخدامها. باستثناء العقد الوهمية ذات الفهارس الأكبر من${\displaystyle n}$ستكون غابة من الأشجار المنفصلة، ​​شجرة لكل بت مُعيّن في التمثيل الثنائي لـ${\displaystyle n}$.

هنا، أسلاف العقدة هي جميع العقد التي تشمل مجاميع نطاقاتها نطاقها. على سبيل المثال،${\displaystyle F[6]}$يحتوي على مجموع${\displaystyle A(4,6]}$،${\displaystyle F[8]}$يحتوي على مجموع${\displaystyle A(0,8]}$وهكذا دواليك.

لتعديل إحدى القيم${\displaystyle A[i]}$أضف التغيير إلى${\displaystyle F[i]}$، ثم${\displaystyle i}$ثم جده، وهكذا، حتى يتجاوز الفهرس${\displaystyle n}$.

على عكس الشجرتين الأخريين، فإن شجرة البحث هذه هي شجرة ثنائية ، مرتبة بترتيب يسميه كنوت "كومة جانبية". ^{[ 5 ]} يُخصص لكل عقدة ارتفاع يساوي عدد الأصفار اللاحقة في التمثيل الثنائي لفهرسها، مع كون الأب والأبناء هم أقرب فهرس (أو فهارس) عدديًا للارتفاع المجاور. العقد ذات الفهارس الفردية (${\displaystyle \operatorname {lsb} (i)=1}$) هي أوراق. العقد ذات الفهارس الزوجية يكون أقرب عقدتين من الفهرس الأدنى التالي بمثابة أبناء لها.${\displaystyle i\pm \operatorname {lsb} (i)/2}$. عقدة${\displaystyle i}$الأصل في شجرة البحث هو${\displaystyle (i-\operatorname {lsb} (i))\mathbin {|} (2\cdot \operatorname {lsb} (i))}$.

على سبيل المثال، أبناء العدد 6 = 110 ₂ هم 5 = 101 ₂ و 7 = 111 ₂ ، ووالده هو 4 = 100 ₂ .

على الرغم من أن هذه الشجرة قد تكون لانهائية، إلا أنه يمكننا تعريف جذرها بأنه أعلى عقدة موجودة ، ويكون فهرسها أكبر قوة للعدد 2 أقل من أو يساوي${\displaystyle n}$.

من الممكن أن يكون للعقدة أب وهمي بفهرس أكبر من${\displaystyle n}$ومع ذلك، لا يزال للعقدة جدٌّ موجود. إذا انطبق المثال أعلاه على شجرة مكونة من 5 عقد، فإن العقدة 5 سيكون لها أبٌ وهمي 6، ولكن جدٌّ موجود 4.

يمكن اعتبار شجرة البحث مزيجًا من الشجرتين السابقتين. تحتوي الشجرة الفرعية اليسرى للعقدة على جميع فروعها في شجرة التحديث، بينما تحتوي شجرتها الفرعية اليمنى على جميع فروعها في شجرة الاستعلام. يكون والد العقدة في شجرة البحث إما والد الاستعلام أو والد التحديث (بحسب ما إذا كانت العقدة فرعًا أيمن أو أيسر على التوالي)، ويمكن العثور على النوع الآخر من الآباء من خلال عدة خطوات تصاعدية في شجرة البحث.

مع ذلك، فإن عمليات التصفح التصاعدي في شجرة البحث غير شائعة؛ إذ يُستخدم بشكل أساسي لإجراء استعلامات الترتيب: عند إعطاء مجموع بادئة، ما هو فهرس ظهوره؟ ويتم ذلك من خلال تصفح تنازلي عبر شجرة البحث. أثناء التصفح، يتم الاحتفاظ بثلاثة متغيرات: فهرس العقدة الحالية، والترتيب المطلوب في الشجرة الفرعية المتفرعة من العقدة الحالية، و"فهرس احتياطي" يُعاد إذا كان الترتيب المطلوب أكبر من الترتيب الموجود في الشجرة الفرعية.

في البداية، تكون العقدة الحالية هي الجذر، والرتبة المطلوبة هي الاستعلام الأصلي، وفهرس الاحتياط هو قيمة "تجاوز" خاصة تشير إلى أن الرتبة غير موجودة في الشجرة. (بحسب التطبيق،${\displaystyle 0}$أو${\displaystyle n+1}$(يمكن استخدامها لهذا الغرض.)

في كل خطوة، إما أن تكون العقدة الحالية عقدة وهمية (مؤشر أكبر من${\displaystyle n}$أو يجب أن نقرر ما إذا كان الموضع المطلوب يقع على يسار أو يمين نهاية العقدة الحالية. إذا كانت الرتبة المطلوبة أقل من قيمة مصفوفة فينويك${\displaystyle F[i]}$بالنسبة للعقدة الحالية، يجب البحث في شجرتها الفرعية اليسرى. إذا كانت أكبر، يتم البحث في شجرتها الفرعية اليمنى. أما إذا كانت مساوية، فيعتمد الاتجاه المختار على كيفية رغبتك في التعامل مع عمليات البحث عن المجاميع الواقعة تمامًا بين عقدتين.

ثم يتم تقسيم هذه الاحتمالات الثلاثة بشكل أكبر بناءً على ما إذا كانت العقدة الحالية ورقة أم لا:

• إذا كانت العقدة الحالية عقدة طرفية و:
  • الهدف موجود في الشجرة الفرعية اليسرى (الفارغة)، أعد الفهرس الحالي.
  • إذا كان الهدف وهميًا أو موجودًا في الشجرة الفرعية اليمنى، فأرجع فهرس الاحتياط.
• إذا لم تكن العقدة الحالية عقدة طرفية و:
  • إنه وهمي، ابحث عن نفس الرتبة في شجرته الفرعية اليسرى مع فهرس احتياطي لم يتغير.
  • إذا كان الهدف موجودًا في الشجرة الفرعية اليسرى، فابحث عن نفس الرتبة في الشجرة الفرعية اليسرى باستخدام الفهرس الحالي كفهرس احتياطي.
  • إذا كان الهدف موجودًا في الشجرة الفرعية اليمنى، فابحث عن رتبة الهدف مطروحًا منها قيمة العقدة الحالية في الشجرة الفرعية اليمنى، مع بقاء فهرس التراجع دون تغيير.

إحدى الخوارزميات البسيطة لإنشاء شجرة فينويك هي تهيئة الشجرة بقيم فارغة وتحديث كل فهرس على حدة. يعمل هذا الحل في${\displaystyle O(n\log {n})}$الوقت، ولكن${\displaystyle O(n)}$البناء ممكن: ^{[ 6 ]}

الدالة construct(values) هي tree := values لكل فهرس من 1 إلى حجم(الشجرة) نفّذ parentIndex := index + lsb(index) إذا كان parentIndex < size(tree) tree[parentIndex] += tree[index] شجرة العودة