😗 😟 ✍️ फेनविक वृक्ष 😁 🧑 📵

नमस्कार, हबहार। अब मैं इस तरह के डेटा संरचना के बारे में बात करना चाहता हूं जैसे कि फेनविक पेड़। पहली बार 1994 में पीटर फेनविक द्वारा वर्णित। यह संरचना सेगमेंट के पेड़ के समान है, लेकिन इसे लागू करना आसान है।

यह क्या है

फेनविक ट्री एक डेटा संरचना है, एक सरणी पर एक पेड़ जिसमें निम्नलिखित गुण होते हैं:

• आप किसी भी खंड पर कुछ प्रतिवर्ती संचालन एफ के मूल्य की गणना करने की अनुमति देता है [एल; आर] लघुगणकीय समय के लिए;

• आपको ओ (लॉग एन) से परे किसी भी तत्व के मूल्य को बदलने की अनुमति देता है;

• ओ (एन) मेमोरी की आवश्यकता होती है;

ऑपरेशन एफ

ऑपरेशन एफ को अलग-अलग तरीकों से चुना जा सकता है, लेकिन सबसे अधिक बार संचालन अंतराल, अंतराल के उत्पाद के साथ-साथ एक निश्चित संशोधन और प्रतिबंधों के साथ अधिकतम और अंतराल या अन्य संचालन पर न्यूनतम खोजने का योग है।

सरल कार्य

किसी सरणी के लगातार तत्वों का योग खोजने की समस्या पर विचार करें। यह देखते हुए कि फॉर्म (L, R) के कई प्रश्न होंगे, जहां एस (L, R) - [L] से [A] समावेशी सभी तत्वों का योग खोजना आवश्यक है।

इस समस्या का सबसे सरल समाधान आंशिक मात्रा में खोजना है। उन्हें खोजने के बाद, हम इन राशियों को एक सरणी में लिखते हैं जिसमें योग [i] = एक [1] + एक [2] ... + एक [i]। फिर अनुरोध में आवश्यक S (L, R) = sum [R] -sum [L-1] (योग [0] को आमतौर पर शून्य के बराबर माना जाता है, ताकि व्यक्तिगत मामलों पर विचार न किया जाए)।

कमियों

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

लाभ

इस डिजाइन का मुख्य लाभ कार्यान्वयन की सादगी और अनुरोधों की प्रतिक्रिया की गति (ओ (1) के लिए) है।

इस कार्य के लिए फेनविक वृक्ष अनुप्रयोग

हम फ़ंक्शन G (x) का परिचय देते हैं, जिसे प्राकृतिक संख्याओं में परिभाषित किया गया है, और x & (x + 1) के बराबर है (और बिटवाइज़ है)। इस प्रकार, जी (एक्स) एक्स के बराबर है अगर, एक्स के द्विआधारी विस्तार में, अंतिम 0 है (एक्स 2 से विभाज्य है)। और अगर निचले अंकों में x के द्विआधारी विस्तार में इकाइयों का एक समूह है, तो फ़ंक्शन x के साथ x के बराबर अंतिम इकाइयों के साथ है। आप उदाहरणों से सत्यापित कर सकते हैं कि यह x (x + 1) है (आंकड़ा देखें)।

बिटवाइज़ एंड

अब हम निम्नलिखित आंशिक रकमों पर विचार करेंगे और उन्हें t [i] = a [G [i]] + + [a [G [i] +1] ... + a [i] में लिखेंगे। अगला, यह दिखाया जाएगा कि इन राशियों को कैसे खोजना है।

राशि की गणना

एस (एल, आर) को खोजने के लिए, हम एस (1, एल -1) और एस (1, आर) की खोज करेंगे। हम एक फ़ंक्शन लिखते हैं, जो कि सरणी t की उपस्थिति में, S (L, R) को खोजेगा। इस मामले में, बाएं छोर को राशि में शामिल नहीं किया जाएगा, लेकिन यदि कार्य में यह आवश्यक है तो इसे शामिल करना आसान है (कोड देखें)।

const int N=100; int t[N],a[N]; int sum(int L, int R) { int res=0; while (R >= 0) { res += t[R]; R = G( R ) - 1; } while (L >= 0) { res -= t[L]; L = G(L) - 1; } return res; }

यह भी ध्यान देने योग्य है कि प्रत्येक अनुप्रयोग के लिए फ़ंक्शन जी बाइनरी नोटेशन x में इकाइयों की संख्या को कम से कम 1 से कम कर देता है। जिसमें से यह निम्नानुसार है कि कुल की गणना O (लॉग एन) में की जाएगी।

तत्वों का संशोधन

अब तत्वों के संशोधन पर विचार करें। हमें यह जानने की जरूरत है कि तत्वों को कैसे बदला जाए, इसके आधार पर आंशिक मात्रा में जल्दी से कैसे बदलें हम d द्वारा एक [k] बदल देंगे। फिर हमें सरणी के तत्वों को बदलने की जरूरत है [j] जिसके लिए असमानता G (j) <k <j सत्य है। लेकिन फिर निम्नलिखित चाल बचाव के लिए आता है। यह कहा गया है कि सभी मांगे गए जे अनुक्रम सी [i] (गणना देखें) से संबंधित होंगे।

फेनविक वृक्ष

जहां के तहत | बिटवाइज़ OR समझें।

बिटवार या

यह नोटिस करना आसान है कि यह फ़ंक्शन सख्ती से बढ़ता है और सबसे खराब स्थिति में, समय का लघुगणक लागू किया जाएगा, क्योंकि यह नंबर k के बाइनरी विस्तार में प्रत्येक बार एक इकाई जोड़ता है।

हम एक फ़ंक्शन लिखते हैं जो एक [k] तत्व को d से बदल देगा, और एक ही समय में संबंधित आंशिक रकम को बदल देगा।

 const int N=100; int t[N],a[N]; void upd(int k, int d) { a[k]+=d; while(k<N) { t[k]+=d; k=(k|(k+1)); } }

प्रारंभ

अब ध्यान दें कि सरणी टी की प्रारंभिक गणना के दौरान, इसे शून्य से प्रारंभ करना संभव है। उसके बाद, हम प्रत्येक एन तत्वों के लिए एप्लिकेशन (i, [[i]) फ़ंक्शन का उपयोग करते हैं। फिर, प्रारंभिक गणना ओ (एन * लॉग एन) समय लेगी, जो सरल आंशिक रकम के साथ वर्णित एल्गोरिदम से अधिक है।

रेखा के पेड़ के साथ तुलना

फायदे:

- पहले से ही सादगी और गति का उल्लेख किया

- मेमोरी O (N) लेता है

नुकसान:

- फ़ंक्शन को प्रतिवर्ती होना चाहिए, जिसका अर्थ है कि यह पेड़ न्यूनतम और अधिकतम (जब तक हम कुछ डेटा का त्याग नहीं कर सकते) की गणना नहीं कर सकते।

निष्कर्ष

हमने तत्वों के योग के बारे में प्रश्नों का उत्तर देना और किसी तत्व को लघुगणक समय में संशोधित करना सीखा है। इस एल्गोरिथ्म के कई उपयोग हैं, और उन सभी कार्यों में मदद कर सकते हैं जहां आपको ऑपरेशन के परिणाम को जल्दी से बदलने और निर्धारित करने की आवश्यकता होती है। मुझे उम्मीद है कि हर कोई समझ गया और दिलचस्प होगा। आपका ध्यान देने के लिए धन्यवाद।

फेनविक वृक्ष