अधिकतम के लिए फेनविक वृक्ष

फेनविक वृक्ष के बारे में बहुत से लोग जानते हैं। कई इसका इस्तेमाल करते हैं। हालांकि, यह माना जाता है कि फेनविक वृक्ष अधिकतम / न्यूनतम नहीं पाया जा सकता है।
जैसे, इस ऑपरेशन का कोई उलटा नहीं है। हालांकि, एल्गोरिथ्म में छोटे बदलाव हमें इस समस्या को हल करने की अनुमति देते हैं।
एनबी: लेख उन लोगों के लिए लिखा गया है, जो जानते हैं कि फेनविक वृक्ष क्या है और अधिकतम के लिए इसके संशोधन का वर्णन करता है। जो लोग नहीं जानते कि फेनविक वृक्ष क्या है, इसके बारे में कहीं कहीं पढ़ने के लिए सिफारिश की जाती है, यहां तक ​​कि कोर्मेन में भी, यहां तक ​​कि हब पर लेख में भी।

1. समस्या का विवरण

एक सरणी है। इसके लिए बहुत सारे अनुरोध किए जाते हैं, दोनों अंतराल में अधिकतम खोजने के लिए और कोशिकाओं में से एक में मूल्य बढ़ाने के लिए।
हां, यह एक वृद्धि है। सेल में मान कम नहीं किया जा सकता है, अन्यथा एल्गोरिथ्म काम नहीं करता है।

2. दरअसल एल्गोरिथ्म

चलो एक वर्ग बनाते हैं - फेनविकट्री, जिसमें दो विधियाँ होंगी - अपडेट (इंट आई, डबल कॉस्ट) और मैक्स (इंट लेफ्ट, इंट राइट) - क्रमशः आई-थ सेल में मानों को अपडेट करें और अंतराल में अधिकतम खोजें।
फ़ेनविक पेड़ में हमेशा की तरह, हमें एक k- न्यूनतम संख्या की आवश्यकता है जैसे कि pow (2, k)> = a.size ()
हम एक सरणी में पेड़ को संग्रहीत करेंगे।

सामान्य फेनविक वृक्ष से मुख्य अंतर

हमें दो सरणियों की आवश्यकता है, और एक नहीं, जैसा कि सामान्य फेनविक पेड़ में है, चलो उन्हें बाएं और दाएं कहते हैं
सरणी के ith सेल में हम सेगमेंट पर अधिकतम स्टोर करेंगे [iG (i) + 1, i], सरणी के ith सेल में हम सेगमेंट पर अधिकतम स्टोर करेंगे [i, i + G (i) -1] i <pow (2, के) और सेगमेंट पर [i, i] i = pow (2, k) के लिए।

वास्तव में वर्ग:

class FenwickTree { private: vector<double> a; vector<double> left; vector<double> right; public: void PreProc(); double Max(int left,int right); void Update(int i,double cost); }; 

प्रीप्रोक () फ़ंक्शन को पेड़ से हमारे प्रारंभिक डेटा को जोड़ने की आवश्यकता है और यह उचित रूप से जटिल दिखता है:

 void FenwickTree::PreProc(){ for(int i=0;i<a.size();i++) Update(i+1,a[i]); } 

मैं आपका ध्यान आकर्षित करता हूं, यह i + 1 है, क्योंकि सरणियों G (x) = x- (x & (x-1)) में हमारा संक्रमण कार्य x> 0 के लिए काम करता है
अब अद्यतन फ़ंक्शन लिखते हैं:

 void FenwickTree::Update(int r,double cost) { a[r-1]=cost; int i=r; while(i<=pow(2.0,double(k))) { left[i]=max(left[i],cost); i=i+G(i); } i=r; while(i>0) { right[i]=max(right[i],cost); i=iG(i); } } 

और अधिकतम:

 double FenwickTree::Max(int l,int r){ double res=0; int i=l; while(i+G(i)<=r) { res=max(res,right[i]); i=i+G(i); } if(a[i-1]>res) ans=i; res=max(res,a[i-1]); i=r; while(iG(i)>=l) { res=max(res,left[i]); i=iG(i); } return res; } 

वह सब है।

जैसा कि आप देख सकते हैं, अधिकतम के लिए फेनविक पेड़ को बहुत ही सरल और बहुत तेज़ी से लिखा जा सकता है (जो कभी-कभी महत्वपूर्ण होता है)।