एक खंड पर संशोधन के साथ फेनविक वृक्ष

यह डेटा संरचना इस पोस्ट में देखी जा सकती है और इसका संशोधन इसमें अधिकतम खोजने के लिए किया जा सकता है। लेकिन मैं एक सेगमेंट में तत्वों में बदलाव के साथ कार्यान्वयन को कभी पूरा नहीं कर पाया, इसलिए मैंने खुद को पाने में कामयाब होने के लिए साझा करने का फैसला किया।

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

एक सरणी है। आपको दो प्रकार के अनुरोधों को पूरा करने में सक्षम होना चाहिए:

1. संशोधन - सेगमेंट के प्रत्येक तत्व में d जोड़ें [l, r]
2. योग - खंड के तत्वों की राशि की गणना [l, r]

2. समाधान का विवरण

यह देखना आसान है कि खंड [0, r] को खंड [l, r] को दो उपसर्गों में तोड़कर दोनों प्रकार के प्रश्नों को "सुगम" बनाया जा सकता है। सेगमेंट के पेड़ के लिए, हम एक दूसरा एरे बनाएंगे, जिसमें हम यह स्टोर करेंगे कि इस सेगमेंट के सभी नंबरों में कितना जोड़ा जाए।

भविष्य के तरीकों के प्रोटोटाइप के साथ एक फेनविक वर्ग बनाएं।

class Fenwick{ int *m, *mt, N; public: Fenwick(int n); Fenwick(int a[], int n); void add_range(int r, int d); void add_range(int l, int r, int d); int sum(int r); int sum(int l, int r); }; 

पहले निर्माता में, यह मेमोरी आवंटित करने और सरणी के तत्वों को रीसेट करने के लिए पर्याप्त है। और दूसरे में, हम एक सरणी से गुजरते हैं और पेड़ में मूल्यों को आराम करते हैं।

 Fenwick::Fenwick(int n){ N = n; m = new int[N]; mt = new int[N]; memset(m, 0, sizeof(int)*N); memset(mt, 0, sizeof(int)*N); } Fenwick::Fenwick(int a[], int n){ N = n; m = new int[N]; mt = new int[N]; memset(m, 0, sizeof(int)*N); memset(mt, 0, sizeof(int)*N); for(int i=0;i<N;++i){ m[i] += a[i]; if((i|(i+1))<N) m[i|(i+1)] += m[i]; } } 

अब परिवर्तन ऑपरेशन पर विचार करें। मान लीजिए कि अनुरोध "खंड के तत्वों में 1 जोड़ दें [0, 9]"। यह खंड पूरी तरह से असंतुष्ट खंडों [0, 7] और [8, 9] से आच्छादित है, इसलिए, तत्वों 7 और 9 में हम सरणी mt 1 के तत्वों को जोड़ते हैं। लेकिन ऐसे खंड हैं जिनमें [0, 9] (या इसका एक हिस्सा) एक उप-खंड के रूप में है। ये सभी दाईं ओर स्थित हैं। उनके लिए, सरणी में मूल्य में परिवर्तन करना आवश्यक है, क्योंकि खंड के कई तत्वों [0, 9] में वे शामिल हैं। अर्थात्, 2 से m [11] और 10 से m [15] जोड़ें।



यह आंकड़ा से देखा जा सकता है कि आंदोलनों को उसी कानूनों के अनुसार होता है जैसा कि फेनविक पेड़ के तुच्छ कार्यान्वयन में होता है, इसलिए हम तुरंत कोड की ओर मुड़ते हैं।

 void Fenwick::add_range(int r, int d){ if(r<0) return ; for(int i=r;i>=0;i=(i&(i+1))-1) mt[i] += d; for(int i=r|(r+1);i<N;i|=i+1) m[i] += d*(r-(i&(i+1))+1); } void Fenwick::add_range(int l, int r, int d){ add_range(r, d); add_range(l-1, -d); } 

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

 int Fenwick::sum(int r){ if(r<0) return 0; int res = 0; for(int i=r;i>=0;i=(i&(i+1))-1) res += m[i] + mt[i]*(i-(i&(i+1))+1); for(int i=r|(r+1);i<N;i|=i+1) res += mt[i]*(r-(i&(i+1))+1); return res; } int Fenwick::sum(int l, int r){ return sum(r) - sum(l-1); } 

3. सारांश

हम ओ (एन) में संशोधन के साथ एक डेटा संरचना प्राप्त करने में कामयाब रहे, संशोधन और हे (लॉगएन) में सेगमेंट पर राशि। 10,000,000 तत्वों और 10,000,000 अनुरोधों के साथ एक यादृच्छिक परीक्षण पर, मुझे निम्नलिखित संख्याएं प्राप्त हुईं:

डेटा संरचना	प्रारंभ	परिवर्तन	योग
Fenwick	0.13 एस	9.12 एस	8.90 एस
RSQ ( ई-मैक्स के साथ कार्यान्वयन )	0.25 एस	17.13 एस	13.53 से