Sqrt अपघटन

परिचय

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

समस्या का औपचारिक विवरण

एक सरणी A [0..n-1] को देखते हुए, हमें यह जानने की जरूरत है कि मनमाने ढंग से l और r के लिए A [l..r] तत्वों की राशि की कुशलता से गणना कैसे की जाए जो कि सरणी की सीमा से आगे न जाएं। व्यापकता के नुकसान के बिना, हम मानते हैं कि l <= r ।

निर्णय

हम Sqrt अपघटन विधि का उपयोग करते हैं। यह विधि आपको समस्या को हल करने की अनुमति देती है । विधि का सार यह है कि हम मूल सरणी को लंबाई के ब्लॉक में विभाजित करते हैं और कुछ पूर्व-गणना करें। जाहिर है, ऐसे ब्लॉक काम करेंगे टुकड़े। अंतिम ब्लॉक दूसरों से छोटा हो सकता है यदि n पूरी तरह से विभाज्य नहीं है लेकिन चिंता की कोई बात नहीं है।

ब्लॉक की लंबाई दें len = (हम मानते हैं कि मूल मूल्य गोल है)।


और अगर n लेन से पूरी तरह से विभाज्य नहीं है, तो अंतिम ब्लॉक की लंबाई लेन नहीं होगी, लेकिन कम। जो, जैसा कि पहले उल्लेख किया गया है, महत्वपूर्ण नहीं है।

अगला, B [i] में एक सरणी B बनाएं, हम i-th ब्लॉक के तत्वों का योग संचित करेंगे। जाहिर है, ऐसा अनुमान लगेगा समय है, इसलिए हमें सिर्फ ए के माध्यम से जाना होगा।

इसलिए, राशि का अनुरोध करते समय, हमें एल से आर तक के सभी तत्वों के माध्यम से चलाने की आवश्यकता नहीं है, क्योंकि हमने पहले से ही आंशिक नंबरों की गणना की है। एक उदाहरण पर विचार करें।

A = {3, 4, 8, 7, 1, 6, 1, 6}, फिर len = 3, B [0] = 15, B [1] = 14, B [2] = 7।
और वे हमें पहली से छठी (हम खरोंच से संख्या) के तत्वों का योग पूछते हैं।



सबसे पहले, हमें ईमानदारी से सरणी के दो तत्वों पर जाना है और 4 और 8 को जोड़ना है, क्योंकि हमें पूर्ण योग बी [0] की आवश्यकता नहीं है, लेकिन केवल एक हिस्सा है। अगला, हमें सरणी के माध्यम से चलाने की आवश्यकता नहीं है, क्योंकि बी [1] पहले से ही गिना गया है और 14 के बराबर है, और अंत में 1 जोड़ते हैं, जैसे कि चल रहा है, क्योंकि हमें अंतिम ब्लॉक की पूरी राशि की आवश्यकता नहीं है।

कार्यान्वयन:

// हमारे पास एक सरणी ए (दी गई) है और बी आंशिक रकम का एक सरणी है।
// लेन - ब्लॉक लंबाई

for (int i = 0; मैं <n; i ++)
बी [आई / लेन] + = ए [आई]; // ब्लॉकों की राशि की गणना करें

// एल और आर सीमाएं हैं

int i = l, sum = 0;
जबकि (i <= r)
{
अगर (i% len == 0 && i + len -1 <= r)
{
sum + = B [i / len];
i + = लेन;
}
अन्यथा
{
sum + = A [i];
मैं ++;
}
}

परिणाम होगा।

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