डायनामिक प्रीफिक्स योग और वेटेड सेलेक्शन के लिए Fenwick Tree कैसे लागू करें?

1. प्रश्न

आपके पास लंबाई n की एक डायनामिक फ्रीक्वेंसी टेबल है। विभिन्न स्थितियों पर मान अक्सर बढ़ाए जाते हैं, और सिस्टम को प्रीफिक्स योग, रेंज योग का उत्तर देना होगा, और संचयी वजन की k-वीं इकाई वाली स्थिति का पता लगाना होगा। O(log n) पॉइंट अपडेट और प्रीफिक्स प्रश्नों के साथ एक Fenwick Tree (बाइनरी इंडेक्सड ट्री) लागू करें, और इसकी तुलना एक सामान्य प्रीफिक्स एरे और एक सेगमेंट ट्री से करें।

2. बाधाएं और स्पष्टीकरण

• आंतरिक रूप से वन-बेस्ड इंडेक्सिंग का उपयोग करें; एक सार्वजनिक API ज़ीरो-बेस्ड स्थितियों को स्वीकार कर सकता है लेकिन उसे ठीक एक बार परिवर्तित करना चाहिए।
• अपडेट डेल्टा या किसी नए मान से अंतर हो सकते हैं; बताएं कि क्या नकारात्मक मानों की अनुमति है।
• रैंक 1 से शुरू होती हैं। वेटेड सेलेक्शन केवल तभी परिभाषित होता है जब सभी वजन गैर-नकारात्मक हों और कुल कम से कम k हो।
• पहले सिंगल-थ्रेडेड संरचना पर चर्चा करें; समवर्ती (concurrent) अपडेट के लिए लॉक या शार्डिंग की आवश्यकता होती है और यह नहीं माना जा सकता कि सामान्य पूर्णांक राइट्स एक सुसंगत स्नैपशॉट बनाते हैं।

3. मुख्य विचार

एंट्री i एक निरंतर रेंज के योग को संग्रहीत करती है जिसकी लंबाई lowbit(i) = i & -i है। एक प्रीफिक्स क्वेरी बार-बार lowbit घटाती है, जबकि एक पॉइंट अपडेट बार-बार lowbit जोड़ता है, इसलिए प्रत्येक O(log n) एरे स्थितियों को छूता है। एक रेंज योग दो प्रीफिक्स का अंतर होता है। जब प्रारंभिक एरे ज्ञात हो, तो O(n) में निर्माण करने के लिए प्रत्येक मान को उसके पैरेंट इंडेक्स में प्रचारित (propagate) करें।

4. संदर्भ कार्यान्वयन

class Fenwick:
  init(values):
    tree = [0] * (len(values) + 1)
    for i from 1 to len(values):
      tree[i] += values[i - 1]
      parent = i + lowbit(i)
      if parent < len(tree):
        tree[parent] += tree[i]

  add(index0, delta):
    i = index0 + 1
    while i < len(tree):
      tree[i] += delta
      i += lowbit(i)

  prefixSum(index0Exclusive):
    total = 0
    i = index0Exclusive
    while i > 0:
      total += tree[i]
      i -= lowbit(i)
    return total

  rangeSum(left0, right0Exclusive):
    return prefixSum(right0Exclusive) - prefixSum(left0)

वेटेड सेलेक्शन के लिए, उच्चतम बाइनरी स्टेप से जांचें। यदि उम्मीदवार इंडेक्स पर जाने से संचयी योग k से नीचे रहता है, तो उस चरण को स्वीकार करें और उसके योग को k से घटाएं; अंतिम इंडेक्स प्लस वन वह स्थिति है जिसमें रैंक k शामिल है। इसके लिए मोनोटोनिक संचयी योग की आवश्यकता होती है और इसलिए इसे सीधे नकारात्मक वजनों के साथ उपयोग नहीं किया जा सकता है।

5. जटिलता और ट्रेड-ऑफ

एक Fenwick Tree एक O(n) एरे का उपयोग करता है। पॉइंट एडिशन, प्रीफिक्स योग और वेटेड सेलेक्शन O(log n) हैं, जबकि लीनियर निर्माण O(n) है। यह सेगमेंट ट्री की तुलना में अधिक कॉम्पैक्ट है और अक्सर इसमें छोटे स्थिरांक (constants) होते हैं, लेकिन यह रेंज मिनिमा, जटिल रेंज अपडेट, या समृद्ध सेगमेंट मेटाडेटा के बजाय स्वाभाविक रूप से प्रतिवर्ती प्रीफिक्स एग्रीगेट्स को व्यक्त करता है। केवल पढ़ने योग्य (read-only) डेटा के लिए, एक सामान्य प्रीफिक्स एरे O(1) में प्रश्नों का उत्तर देता है; जब अपडेट बार-बार होते हैं तब Fenwick मूल्यवान हो जाता है।

6. सत्यापन और अवलोकनीयता

• यादृच्छिक (random) इनपुट पर, जिसमें खाली, सिंगलटन और अंतिम-इंडेक्स मामले शामिल हैं, एक सरल एरे के साथ प्रत्येक add, prefixSum, और rangeSum की तुलना करें।
• सभी शून्य, बहुत बड़े वजन, ठीक k के बराबर कुल, सीमा से बाहर k, और अमान्य इंडेक्स का परीक्षण करें।
• बार-बार पॉइंट एडिशन के विरुद्ध लीनियर निर्माण की क्रॉस-जांच करें और आंतरिक एरेज़ और क्वेरी परिणामों दोनों की तुलना करें।
• वेटेड सेलेक्शन के लिए गैर-नकारात्मक यादृच्छिक वजन उत्पन्न करें और प्रत्येक k के लिए प्रीफिक्स सीमाओं की जांच करें; नकारात्मक-वजन वाले इनपुट को अलग से अस्वीकार करें।

7. सामान्य गलतियाँ

• ज़ीरो-बेस्ड और वन-बेस्ड इंडेक्स को मिलाना ताकि स्थिति शून्य छूट जाए या अंतिम स्थिति ओवरफ्लो हो जाए।
• यह समझाए बिना कि यह सबसे निचले बाइनरी ब्लॉक को निकालता है, i & -i को केवल एक नेगेशन ट्रिक मानना।
• नकारात्मक मानों के साथ वेटेड सेलेक्शन का उपयोग करना, भले ही संचयी योग अब मोनोटोनिक न रहे हों।
• अपडेट पाथ के साथ डेल्टा जोड़ने के बजाय ट्री नोड को नए मान से ओवरराइट करना।

8. साक्षात्कार स्कोरिंग बिंदु

lowbit और रेंज कवरेज की व्याख्या करता है

उम्मीदवार को यह बताना चाहिए कि प्रत्येक नोड कौन सी निरंतर रेंज संग्रहीत करता है और क्वेरीज़ और अपडेट lowbit जंप का पालन क्यों करते हैं।

सीमा त्रुटियों (boundary errors) के बिना एक कार्यान्वयन लिखता है

उत्तर में वन-बेस्ड आंतरिक इंडेक्सिंग को बनाए रखना चाहिए, खाली एरे, अमान्य स्थितियों और हाफ-ओपन सीमाओं को संभालना चाहिए, और कभी भी एरे के अंत से आगे एक्सेस नहीं करना चाहिए।

जटिलता और निर्माण प्राप्त करता है

उम्मीदवार को O(log n) क्वेरी, अपडेट और सेलेक्शन लागत, O(n) लीनियर निर्माण देना चाहिए, और प्रीफिक्स एरेज़ और सेगमेंट ट्रीज़ की सीमाओं की तुलना करनी चाहिए।

वेटेड-सेलेक्शन की पूर्व शर्तों को पहचानता है

उत्तर में गैर-नकारात्मक वजन और मोनोटोनिक संचयी योग की आवश्यकता होनी चाहिए, फिर सटीक हिट, ओवरफ्लो और बड़ी संख्या की सीमाओं का परीक्षण करना चाहिए।