प्रीफिक्स सम (Prefix Sum)
प्रीफिक्स सम का इस्तेमाल ऐरे में विभिन्न रेंज के साथ काम करते समय बहुत उपयोगी साबित होता है। अक्सर, हम किसी ऐरे के आंशिक खंड (रेंज) का योग हर बार फिर से निकालने के बजाय उसके प्रीफिक्स सम का इस्तेमाल करके कोड को काफी तेज़ कर सकते हैं।
कल्पना कीजिए कि हमें बहुत सारी क्वेरीज़ (हो सकता है लाखों की संख्या में) का जवाब देना है, जिसमें सवाल है: “ऐरे
a के शुरुआती एलिमेंट्स से लेकर इंडेक्स तक का योग कितना होगा?” अगर हम हर बार सरल (naive) तरीक़े से निकालें, तो बहुत दोहराव होगा। उदाहरण के लिए, अगर हमारे पास ऐरे और क्वेरीज़ इस प्रकार हैं:a = [8, 3, -2, 4, 10, -1, 0, 5] # array
q = [3, 5, 2, 7] # queriesतो हर क्वेरी के लिए
for-लूप चलाकर योग करना पड़ेगा:res1 = a[0] + a[1] + a[2] + a[3]
res2 = a[0] + a[1] + a[2] + a[3] + a[4] + a[5]
res3 = a[0] + a[1] + a[2]
res4 = a[0] + a[1] + a[2] + a[3] + a[4] + a[5] + a[6] + a[7]ध्यान दें कि इन गणनाओं में बहुत-सा हिस्सा दोहराया जाता है। उदाहरण के लिए,
res2 निकालने से पहले हम a[0] + a[1] + a[2] + a[3] पहले ही res1 में निकाल चुके हैं। इसी तरह, res4 निकालने से पहले a[0] + a[1] + a[2] + a[3] + a[4] + a[5] का योग हमारे पास पहले से मौजूद है। बार-बार वही योग करने के बजाय हम इस दोहराव से बच सकते हैं और क्वेरीज़ का जवाब तुरंत दे सकते हैं।इसके लिए हम एक नया ऐरे
p बनाएँगे, जिसमें p के हर एलिमेंट में ऐरे a के 0 से उस इंडेक्स तक के योग की जानकारी होगी। ऐसे में हर क्वेरी का जवाब p के एलिमेंट तक ही सीमित रह जाएगा:p[0] = a[0]
p[1] = a[0] + a[1]
p[2] = a[0] + a[1] + a[2]
p[3] = a[0] + a[1] + a[2] + a[3]
p[4] = a[0] + a[1] + a[2] + a[3] + a[4]
p[5] = a[0] + a[1] + a[2] + a[3] + a[4] + a[5]
p[6] = a[0] + a[1] + a[2] + a[3] + a[4] + a[5] + a[6]
p[7] = a[0] + a[1] + a[2] + a[3] + a[4] + a[5] + a[6] + a[7]ध्यान दीजिए कि
p का अगला एलिमेंट पाने के लिए हम बस p के पिछले एलिमेंट में a का अगला एलिमेंट जोड़ देते हैं, जिससे बार-बार वही जोड़ करने की ज़रूरत नहीं पड़ती:p[0] = a[0]
p[1] = p[0] + a[1]
p[2] = p[1] + a[2]
p[3] = p[2] + a[3]
p[4] = p[3] + a[4]
p[5] = p[4] + a[5]
p[6] = p[5] + a[6]
p[7] = p[6] + a[7]यह पूरा काम एक ही
for-लूप में किया जा सकता है, जिससे बार-बार दोहराए जाने वाले काम से बचा जा सके। एक बार जब आपने प्रीफिक्स सम ऐरे p बना लिया, तो हर क्वेरी का जवाब तुरंत दे सकते हैं, क्योंकि p[i] सीधे a[0] + a[1] + ... + a[i] का योग देता है। इसलिए, हर क्वेरी qᵢ के लिए जवाब बस होगा।क्या आप अब प्रीफिक्स सम ऐरे की गणना कर सकते हैं?
इनपुट
इनपुट की पहली पंक्ति में एक अकेला पूरा मान
n (1 ≤ n ≤ ) दिया गया है। इनपुट की दूसरी पंक्ति में n स्पेस-सेपरेटेड मान हैं, जो ऐरे a के एलिमेंट्स को दर्शाते हैं ()।आउटपुट
प्रोग्राम को ऐरे a का प्रीफिक्स सम ऐरे आउटपुट करना चाहिए।
उदाहरण
Input | Output |
8
8 3 -2 4 10 -1 0 5 | 8 11 9 13 23 22 22 27 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 20 MB