एक पूर्णांक सरणी

Question

में उप-सरणी योग ढूँढना एन सकारात्मक पूर्णांक की एक सरणी को देखते हुए। इसमें n*(n+1)/2 उप-सरणी हो सकती है जिसमें एकल तत्व उप-सरणी शामिल हैं। प्रत्येक उप-सरणी में S है। सभी उप-सरणी के लिए S's खोजें O(n^2) उप-सरणी की संख्या O(n^2) है। कई रकम S's भी दोहराया जा सकता है। O(n logn) में सभी अलग-अलग योगों की गणना करने के लिए कोई तरीका नहीं है (रकम के सटीक मूल्य नहीं बल्कि केवल गिनती है)।

मैंने एक दृष्टिकोण की कोशिश की लेकिन रास्ते पर फंस गया। मैंने इंडेक्स 1 से एन तक सरणी को पुन: सक्रिय किया।
कहें a[i] दिया गया सरणी है। प्रत्येक इंडेक्स i, a[i] सभी रकम में जोड़ देगा जिसमें a[i-1] शामिल है और इसमें व्यक्तिगत तत्व भी शामिल होगा। लेकिन अगर डुप्लिकेट a[i-1] शामिल है, तो डुप्लिकेट उभरा होगा, दो रकम का अंतर a[i] है। मेरा मतलब है कि, Sp और Sqa[i-1] पर समाप्त होता है और दोनों का अंतर a[i] है। फिर Sp + a[i]Sq के बराबर है, जो डुप्लिकेट के रूप में Sq दे रहा है।

कहें C[i] अलग-अलग रकम की गणना है जिसमें a[i] पर समाप्त होता है।
तो C[i] = C[i-1] + 1 - numbers of pairs of sums in which a[i-1] is involved whose difference is a[i]।

लेकिन समस्या O(log n) में जोड़े की संख्या का हिस्सा खोजने के लिए है। कृपया मुझे इसके बारे में कुछ संकेत दें या यदि मैं गलत तरीके से हूं और पूरी तरह से अलग दृष्टिकोण की आवश्यकता है तो समस्या को इंगित करें।

Answer 1

जब एस बहुत बड़ा नहीं होता है, तो हम एक (तेज़) बहुपद गुणा के साथ अलग-अलग रकम गिन सकते हैं। जब एस बड़ा होता है, तो एन उम्मीदवार रूप से एक वर्गिक एल्गोरिदम का उपयोग करने के लिए काफी छोटा होता है।

x_1, x_2, ..., x_n सरणी तत्व बनें। Y_0 = 0 और y_i = x_1 + x_2 + ... + x_i दें। चलो पी (z) = z^{y_0} + z^{y_1} + ... + z^{y_n}। बहुपद पी (जेड) * पी (z^{- 1}) के उत्पाद की गणना करें; के^0 के साथ z^k का गुणांक nonzero है और केवल अगर के उप-सरणी राशि है, तो हमें केवल सकारात्मक शक्तियों के nonzero गुणांक की संख्या को पढ़ना होगा। जेड की शक्तियां, इसके अलावा, एसएस से एस तक होती हैं, इसलिए गुणा को एस लॉग एस

Answer 2

के क्रम में समय लगता है आप उप-सरणी को एक प्रकार के पेड़ के रूप में देख सकते हैं। इस अर्थ में कि [0,3] को उपरोक्त [0,1] और [2,3] पर विभाजित किया जा सकता है।

तो एक पेड़ का निर्माण करें, जहां नोड्स को उपन्यास की लंबाई से परिभाषित किया जाता है और यह मूल सरणी में ऑफ़सेट दिख रहा है, और जब भी आप एक उपरागर की गणना करते हैं, तो इस पेड़ में परिणाम संग्रहित करें।

उप-सरणी की गणना करते समय, आप मौजूदा पेड़ वाले मानों के लिए इस पेड़ को देख सकते हैं।

साथ ही, जब विभाजित हो, तो सरणी के कुछ हिस्सों को विभिन्न CPU कोरों पर गणना की जा सकती है, यदि यह मायने रखती है।

यह समाधान मानता है कि आपको एक ही समय में सभी मूल्यों की आवश्यकता नहीं है, बल्कि विज्ञापन-प्रसार। पूर्व के लिए, कुछ बेहतर समाधान हो सकता है।

इसके अलावा, मुझे लगता है कि हम 10000 के दशक में तत्वों की संख्या के बारे में बात कर रहे हैं। अन्यथा, ऐसा काम एक अच्छा व्यायाम है लेकिन इसमें व्यावहारिक मूल्य नहीं है।