Sqrt अपघटन (रूट अनुकूलन)

Sqrt अपघटन एक विधि, या डेटा संरचना है, जो आपको ऑनलाइन संचालन करने की अनुमति देता है जैसे कि प्रति सेगमेंट की राशि की गणना और आइटम अद्यतन के लिए । अधिक कुशल संरचनाएं हैं, जैसे कि फेनविक पेड़ या खंडों का वृक्ष , जो दोनों अनुरोधों में प्रक्रिया करते हैं । हालांकि, मैं रूट ऑप्टिमाइज़ेशन के बारे में बात करना चाहता हूं, क्योंकि इस पद्धति का एक विचार है जो एक अलग प्रकार के कार्यों पर लागू होता है।

समस्या का बयान

हमें एक सरणी A [i] दी जाती है, जिससे फॉर्म के अनुरोध:

• खंड पर राशि की गणना [एल; R] (बाद में, हम यह समझेंगे कि फ़ंक्शन मिनट, अधिकतम, gcd, आदि की गणना इसी तरह की जा सकती है।
• तत्व ए [i] में जोड़ें, डेल्टा

Naive कार्यान्वयन

हम आंशिक मात्रा की एक सरणी की गणना कर सकते हैं, अर्थात्:

for(int j = 0; j < i; j++) B[j] += A[i]; 

और फिर राशि के अनुरोध पर [एल; R], हम B [R] -B [L-1] को वापस करेंगे । हालांकि, एक परिवर्तन का अनुरोध करने पर, इसे आंशिक रकम (इस तत्व से युक्त) के पुनर्गणना की आवश्यकता होगी और, सबसे खराब स्थिति में, आदेश का एक स्पर्शोन्मुख बना देगा यह अच्छा नहीं है।

अपघटन भवन

मुख्य विचार यह होगा कि * = । अर्थात्, अगर हमारे पास है तत्वों, तो हम उन सभी को विभाजित कर सकते हैं ब्लॉक जहां प्रत्येक लंबा है शायद अंतिम को छोड़कर। फिर सभी ब्लॉकों के लिए हम उस पर संख्याओं के योग की गणना करेंगे, आप तुरंत देख सकते हैं कि सहायक सरणी पर कब्जा हो जाएगा स्मृति।
हम sqrtSums [] सरणी के निर्माण का वर्णन करते हैं:

 int len = (int)sqrt(n) + 1; //  "sqrt-" int sqrtSums[MAXN], st = 0; //   for(int i = 0; i < n; i++) sqrtSums[i / len] += A[i]; 

अनुरोध विवरण

राशि अनुरोध (RSQ)

क्वेरी राशि पर विचार करें [एल; आर], इसके लिए "त्वरित" प्रतिक्रिया के लिए, पहले से उपलब्ध जानकारी का अधिकतम उपयोग करना आवश्यक है। जैसा कि हमने कहा है, सम [एल; आर] = सम [0, आर] - सम [0; एल -1]। यह सीखना रहता है कि अनुरोध को कैसे संसाधित किया जाए [0]; आर]। ध्यान दें कि पहले कुछ खंड ([0; len-1], [len; 2*len-1], ...) पूरी तरह से क्वेरी [0] में शामिल होंगे; R], जिसका अर्थ है कि हम sqrtSums[] लिए जानकारी का उपयोग कर सकते हैं , जब से वहाँ हैं )। हालांकि, हमारे पास फ़ॉर्म की "पूंछ" होगी: [k*len; k*len + delta] [k*len; k*len + delta] (डेल्टा <len, क्योंकि अन्यथा, हम एक और खंड [k*len; (k+1)*len-1] ) शामिल कर सकते हैं, हम इसे मैन्युअल रूप से गणना कर सकते हैं (डेल्टा <len; स्पर्शोन्मुख पर, प्रभावित नहीं करेगा)। यहाँ एक उदाहरण कार्यान्वयन है:

 int getPartSum(int r) { int it = 0, res = 0; while((it+1) * len -1 <= r) res += sqrtSums[it++]; //  ,   for(int i = it*len; i <=r; i++) res += A[i]; // "" return res; } int getSum(int l, int r) { if(l == 0) return getPartSum(r); else return getPartSum(r) - getPartSum(l-1); } 

आइटम परिवर्तन अनुरोध

कई संरचनाओं में, इस क्वेरी को लागू करने के लिए, आपको पेड़ के नीचे जाने की ज़रूरत है, या हैश फ़ंक्शन की गणना करें, या कुछ और ... हालांकि, यहां हमें केवल 2 मान बदलने की आवश्यकता है (प्रत्येक तत्व बिल्कुल एक "sqrt सेगमेंट" में शामिल है)

 int incElement(int index, int delta) { A[index] += delta; sqrtSums[index/len] += delta; } 

रेंज मिन / मैक्स / जीसीडी क्वेरी

RMQ क्वेरीज़ (रेंज मिन / मैक्स क्वेरी) का जवाब देने के लिए आपको लगभग वही चीज़ चाहिए जो रकम के लिए होती है। हालांकि, यह ध्यान देने योग्य है कि आइटम "बेवकूफ" को अपडेट करने के लिए, हमें ज़रूरत है समय (जब एक तत्व को अपडेट करते हुए, पूरे "sqrt सेगमेंट" पर मिनट / अधिकतम का पुनरावर्तन करें), लेकिन अगर हम अपडेट पर कुछ प्रतिबंध लगाते हैं, तो हम एक अनुमान प्राप्त करेंगे । न्यूनतम, अधिकतम / अधिकतम खोजने की समस्या को हल करते समय, केवल तत्व को कम करने / बढ़ाने की अनुमति दें।
न्यूनतम अद्यतन करने के लिए कोड:

 int decElement(int index, unsigned int delta) //delta -     { A[index] -= delta; sqrtSums[index/len] = min(sqrtSums[index/len], A[index]); } 

इसी तरह, अधिकतम अद्यतन करने के लिए:

 int incElement(int index, unsigned int delta) //delta -     { A[index] += delta; sqrtSums[index/len] = max(sqrtSums[index/len], A[index]); } 

यह जोड़ा जाना चाहिए कि आरएमक्यू समस्या में, कार्य कम नहीं होता है [0]; आर] - [0; एल -1], यानी आपको एल से आर तक न्यूनतम / अधिकतम की गणना करनी होगी (फिर से गिनते हुए, "sqrt सेगमेंट" जो कि [L; R] में पूरी तरह से हैं, सोचें कि क्यों विषमता का व्यवहार नहीं बदलेगा, और शुद्ध रनटाइम में भी सुधार हो सकता है ...)।

जीसीडी (ग्रेटेस्ट कॉमन डिविज़र) की गणना करने के लिए, हम "चिप" का उपयोग नहीं कर पाएंगे जो हमने मिनट / अधिकतम के लिए बदल दिया था। इसलिए, दोनों ऑपरेशन के लिए गणना की जाती है ।
GCD के लिए कोड (न्यूनतम और अधिकतम के लिए, getGCD कार्यों को मिनट / अधिकतम द्वारा बदल दिया जाएगा):

 int getGCD(int a, int b) { while(a && b) { if(a < b) b %= a; else a %= b; } return a + b; } int gcdRQ(int l, int r) { int cur_gcd = A[l++]; for(int i = l; i <= r;) if (i % len == 0 && i + len - 1 <= r) { cur_gcd = getGCD(cur_gcd, b[i / len]); i += len; //  "sqrt-" } else cur_gcd = getGCD(cur_gcd, A[i++]); } 

सूत्रों का कहना है

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

अभी के लिए, मुझे आशा है कि यह स्पष्ट था।