कुछ सरणी होने दो। परिवर्तनों की अनुपस्थिति में, हम जल्दी से (एक पंक्ति से तेज) इस सरणी के एक उपखंड पर कुछ कार्यों के मान का पता लगा सकते हैं। ऐसा करने के लिए, हमें अतिरिक्त मेमोरी का उपयोग करने और पूर्व-गणना करने की आवश्यकता है।
उदाहरण के लिए, हमें जल्दी से सरणी के कुछ खंड पर राशि खोजने की आवश्यकता है।
चलिए उपसर्ग योगों की एक सरणी प्राप्त करते हैं, जिसमें सूचकांक i सरणी के सभी तत्वों का योग होगा जिसमें सूचकांक i से कम या उसके बराबर होगा।
ए [] – दी गई सरणी, p[] – उपसर्ग योगों की सरणी
ऐरे काउंट p:
जाहिर है पी [0] = ए [0]। ध्यान दें कि हम p[i] को p[i – 1], क्योंकि i उपसर्ग पर राशि i उपसर्ग पर राशि है – 1 + ए[i]।
इस प्रकार, उपसर्ग योगों की गणना के लिए कोड इस तरह दिखता है:
का उपयोग करके उत्पन्न किया गया
<पूर्व शैली = "मार्जिन-बाएं: 0 पीएक्स; मार्जिन-दाएं: 0 पीएक्स">
int a[n], p[n];
p[0] = a[0< / स्पैन>];
के लिए (int i = 1; i < n; i++)
p[i] = p[i - 1] + a[i];
इसके अलावा, हम ध्यान दें कि खंड पर योग – उपसर्ग पर दो राशियों के बीच का अंतर।
हरा = लाल – नीला
इस प्रकार, यदि अंतराल [l,r] पर योग ज्ञात करना आवश्यक है, तो उत्तर p[r] – पी[एल-1]।
हालाँकि, अगर मैं - 1 तत्व मौजूद नहीं हो सकता है। if’s के बिना करने के लिए, आप 1-इंडेक्सिंग दर्ज कर सकते हैं, और a[0] और p[0] के तटस्थ मान होंगे (0 योग के लिए)।
ध्यान दें कि यह तकनीक समावेशन-बहिष्करण सूत्र का एक विशेष मामला है, इसलिए इस तरह से न केवल रकम, बल्कि गुणा और xor जैसे अन्य कार्यों को भी संग्रहीत करना संभव है।