हमें एक समस्या है कि O(n) स्पर्शोन्मुख से कम में एक स्थिर सरणी a में अंतराल l...r पर योगों की त्वरित गणना कैसे करें।
आइए सरणी a को समान आकार के k ब्लॉक में विभाजित करते हैं और पहले उनमें से प्रत्येक के लिए तत्वों के योग की गणना करते हैं।
अब, अनुरोध का उत्तर देते समय, हम सरणी के तत्वों के माध्यम से जा सकते हैं और उन्हें परिणाम में जोड़ सकते हैं, साथ ही यदि कोई ब्लॉक खंड के अंदर है, तो हम परिणाम में इसका योग जोड़ सकते हैं और छोड़ सकते हैं इस ब्लॉक के तत्व।
इस एल्गोरिथ्म के साथ प्रति क्वेरी संचालन की अधिकतम संख्या n / k + k है, इसलिए इष्टतम k n के वर्गमूल के बराबर है।