द्विआधारी पेड़ कि आंशिक योग संग्रहीत करता है: नाम और मौजूदा कार्यान्वयन

Question

(एक _मैं) n धनात्मक वास्तविक संख्या का एक अनुक्रम, है, और इसकी आंशिक योग अनुक्रम, पर विचार करें (रों _मैं)। यह देखते हुए एक नंबर एक्स ε (0, रों _n], हम खोजने के लिए मैं ऐसी है कि रों_{मैं -1} < एक्स ≤ रों _मैं। इसके अलावा हम _i के सभी आंशिक रकम अपडेट किए बिना किसी को बदलने में सक्षम होना चाहते हैं। दोनों ओ में किया जा सकता है (लॉग n) _i के पत्ते नोड मानों के रूप में, और गैर-पत्ती नोड्स के मान संबंधित बच्चों के मूल्यों का योग होने के साथ एक बाइनरी पेड़ का उपयोग करके समय। यदि n ज्ञात और निश्चित है, तो पेड़ को स्वयं संतुलन नहीं होना चाहिए और एक रैखिक सरणी में कुशलतापूर्वक संग्रहीत किया जा सकता है। इसके अलावा, अगर एन दो की शक्ति है, केवल 2 एन - 1 सरणी तत्वों की आवश्यकता है। ब्लू एट अल।, फिज देखें। रेव ई (1 99 5), पीपी। आर 867-आर 868 एक आवेदन के लिए। समस्या की सामान्यता और समाधान की सादगी को देखते हुए, मुझे आश्चर्य है कि क्या इस डेटा संरचना का एक विशिष्ट नाम है और क्या मौजूदा कार्यान्वयन (अधिमानतः सी ++ में) हैं। मैंने इसे पहले से ही लागू कर लिया है, लेकिन स्क्रैच से डेटा स्ट्रक्चर लिखना हमेशा मुझे पहिया को फिर से शुरू करने जैसा लगता है- अगर कोई पहले ऐसा नहीं करता तो मुझे आश्चर्य होगा।

Answer 1

Fenwick tree (उर्फ बाइनरी अनुक्रमित पेड़) एक डेटा संरचना है जो तत्वों का अनुक्रम बनाए रखती है, और ओ (लॉगन) समय में लगातार तत्वों की किसी भी श्रृंखला के संचयी योग की गणना करने में सक्षम है। किसी एकल तत्व के मूल्य बदलने के लिए ओ (लॉगऑन) समय भी आवश्यक है।

Answer 2

इसे कार्यात्मक प्रोग्रामिंग में finger tree के रूप में जाना जाता है लेकिन स्पष्ट रूप से अनिवार्य भाषाओं में कार्यान्वयन होते हैं। लेखों में blog post का एक लिंक है जो सी # में इस डेटा संरचना के कार्यान्वयन को समझाता है जो आपके लिए उपयोगी हो सकता है।