बीआईटी

Question

का उपयोग कर उलटी गिनती मुझे पता है कि इस प्रश्न पर पहले चर्चा की गई है, लेकिन मुझे बाइनरी इंडेक्सेड ट्री का उपयोग करके ऐसा करने में दिलचस्पी है। मुझे this लिंक यह दिखाने के लिए मिला कि यह कैसे करें। मैंने स्पष्टीकरण का काफी पालन नहीं किया। क्या कोई मुझे एक स्पष्टीकरण दे सकता है कि निम्नलिखित क्यों दिया गया है।

Create a BIT of size greater than n(no of elements). Iterate through array A (
let j be the index of loop),and for each element A[j] do: 

1) Add j-sum(A[j]) to the number of inversions 
2) add(A[j], 1) (i.e. add 1 to the position A[j] on BIT. This effectively 
counts the number of time value A[j] is seen so far) 

मुझे नहीं लगता कि यह क्यों काम करता है।

Answer 1

एक उलटा तब होता है जब कोई तत्व किसी तत्व से बड़ा होता है जो सरणी में इसका अनुसरण करता है।

हम दूसरे तत्व द्वारा समूहित करके इनवर्जनों को गिन सकते हैं। उदाहरण के लिए, सरणी [4, 3, 1, 2] में, तत्व जोड़े (4, 3), (4, 1), (4, 2), (3, 1), और (3, 2) हैं व्युत्क्रम। हम उन्हें दूसरे तत्व से समूहित करते हैं, इसलिए: [[(4, 1), (3, 1)], [(4, 2), (3, 2)], [(4, 3)]]।

हम प्रत्येक तत्व को बदले में देखते हैं, और यह मानते हैं कि यह कितना उलटा है इसका दूसरा तत्व है। उदाहरण में, तत्व 4 0 इनवर्जन में दूसरा तत्व है, तत्व 3 में 1 विवर्तन है, और प्रत्येक 1 में 2 तत्वों में तत्व 1 और 2 है।

किसी दिए गए तत्व को किसी विचलन का दूसरा तत्व होने के लिए, सरणी में कहीं से पहले एक बड़ा तत्व होना चाहिए।

हम बाएं से दाएं सरणी को घुमाने के द्वारा कुशलता से गणना करते हैं और हमेशा बीआईटी का उपयोग करके प्रत्येक मान के कितने तत्वों का सामना करना पड़ता है इसका ट्रैक रखते हुए। प्रारंभ में हमारी आवृत्ति तालिका [0, 0, 0, 0] होगी, क्योंकि हमने कोई तत्व नहीं देखा है। हम 4 पर जाने के बाद, हम इसकी आवृत्ति अपडेट करते हैं, [0, 0, 0, 1] देते हैं। 3, [0, 0, 1, 1], और इतने पर जाने के बाद।

प्रत्येक बार जब हम किसी स्थिति पर जाते हैं, तो हम बीआईटी का उपयोग यह पता लगाने के लिए करते हैं कि अब तक कितने तत्वों का दौरा किया गया है। तो उदाहरण के लिए जब हम 1 का सामना करते हैं, तो बीआईटी में वर्तमान में [0, 0, 1, 1] होता है, जो दर्शाता है कि अब तक शून्य 1 और 2, एक 3 और एक 4 थे। मानों को जोड़कर 0 + 1 + 1 , हम अब तक तत्वों की संख्या की गणना कर रहे हैं एक से अधिक 1.

जोड़ा जा रहा है सभी इन अलग-अलग मायने रखता है व्युत्क्रम की कुल संख्या देता है।

ध्यान दें कि, सामान्य रूप से, आपको प्रभावी होने के लिए समन्वय समन्वयित करना होगा। उदाहरण के लिए, यदि आपके प्रारंभिक सरणी में ए = [9 2, 631, 50, 7] जैसी संख्याएं हैं, तो आपको सैकड़ों तत्वों के साथ बीआईटी आवंटित नहीं करना चाहिए। इसके बजाय, यह निर्धारित करने के लिए सरणी को क्रमबद्ध करें कि 7 631, जो हमें रैंक 7 => 1, 50 => 2, 92 => 3, 631 => 4 असाइन करने की अनुमति देता है; फिर प्रत्येक तत्व को इसके रैंक से प्रतिस्थापित करें, बी = [3, 4, 2, 1] दें। इस सरणी के इनवर्जन की संख्या मूल में समान होगी, क्योंकि बी [i]> बी [जे] अगर और केवल अगर ए [i]> ए [जे]।

(नोट: एक वास्तविक प्रोग्रामर शायद शून्य से शुरू होने वाले सूचकांक का उपयोग करेगा।)