क्रमबद्ध उप-सरणी के kth तत्व को एल से आर तक कैसे जोड़ना है?

Question

समस्या:
हमने आकार N आकार A[] दिया है। अब हम Q प्रश्न दिए जाते हैं, तो हर प्रश्नों तीन पूर्णांक l,r,k से मिलकर बनता है जहां:

1<=l<=r<=N 
1<=k<=(r-l+1) 
1<=N,Q<=10^5 

अब, हम l से r के अनुसार क्रमबद्ध उप सरणी के k तत्व तक योग पता लगाना चाहते हैं।
उदाहरण के लिए:
N=6 और सरणी तत्व हो 5,1,7,4,6,3
और Q=1 जहां l,r,k2,5,3 के रूप में हो।
तो index 2 to index 5 से उप सरणी {1,7,4,6}
छँटाई यह हो जाता है के रूप में {1,4,6,7} तो योग तक k=3 अवधि के लिए (1+4+6)=11
तो जवाब 11 है बराबर है के बाद हो सकता है।

मैंने प्रत्येक उप-सरणी के सॉर्टिंग का उपयोग करने का प्रयास किया है और फिर योग, Q*N*log(N) सबसे खराब मामले में समय जटिलता लेता है।
कृपया सबसे खराब मामले में Q*N से कम समय जटिलता के भीतर कोई बेहतर समाधान खोजने में मदद करें।

Answer 1

एक दृष्टिकोण संशोधन के साथ विलय का उपयोग करके प्रीप्रोसेस करना होगा कि हम सभी क्रमबद्ध मध्यवर्ती परिणामों की प्रतिलिपि रखते हैं।

यह प्रीप्रोकैसिंग ओ (nlogn) लेता है।

मान लीजिए कि हमने 32 तत्वों के साथ शुरुआत की है। अब हम होगा:

• 16 छाँटे गए 2 तत्व सूचियों
• 8 अनुसार क्रमबद्ध 4 तत्व सूचियों
• 4 छाँटे गए 8 तत्व सूचियों
• 2 हल कर 16 तत्व सूचियों
• 1 32 तत्व सूची सॉर्ट किया।

हम ओ (nlogn) में इन सूचियों में से प्रत्येक का उपसर्ग योग भी पूर्ववत कर सकते हैं।

फिर जब एल से आर के लिए एक क्वेरी का सामना करना पड़ा, तो हम प्रीप्रोसेस्ड सूचियों के लॉग (एन) की पहचान कर सकते हैं जो एक साथ एल से आर के सभी तत्वों को कवर करेंगे।

हम फिर मूल्य खोजने के लिए बाइनरी खोज का उपयोग कर सकते हैं जैसे कि पहचान की गई सूचियों में बिल्कुल छोटे तत्व हैं, और योग की गणना करने के लिए उपसर्ग रकम का उपयोग करें।

Answer 2

तो हे (क्यू)> = हे (लॉग एन):

क्रमबद्ध उनके तत्वों की छँटाई आदेश से मूल सरणी सूचकांक, उदाहरण के लिए:

values: [50, 10, 20, 40, 30] -> [10, 20, 30, 40, 50] 
indices: [#0, #1, #2, #3, #4] -> [#1, #2, #4, #3, #0] 

फिर, प्रत्येक प्रश्न के लिए, सॉर्ट किए गए इंडेक्स को दाएं से बाएं स्कैन करें, और पहले k तत्वों के मान जोड़ें जिन्हें आप सामना करते हैं जिनके सूचकांक सीमा के भीतर हैं ([एल, आर])। जटिलता ओ (क्यूएन + एन लॉग एन) = ओ (क्यूएन) होगी - फिर से, बशर्ते कि ओ (क्यू)> = ओ (लॉग एन)।

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