একটি prefix sum array সংগৃহীত মোট সংরক্ষণ করে যাতে যেকোনো range sum O(n) প্রিপ্রসেসিং এর পরে O(1) এ উত্তর দেওয়া যায় — প্রতিটি query এর জন্য O(n) এর পরিবর্তে।
ধারণা
মনে করুন prefix[i] প্রথম i উপাদানের যোগফল। তখন arr[l..r] এর যোগফল হল ।
একটি prefix sum array সংগৃহীত মোট সংরক্ষণ করে যাতে যেকোনো range sum O(n) প্রিপ্রসেসিং এর পরে O(1) এ উত্তর দেওয়া যায় — প্রতিটি query এর জন্য O(n) এর পরিবর্তে।
মনে করুন prefix[i] প্রথম i উপাদানের যোগফল। তখন arr[l..r] এর যোগফল হল ।
prefix[r+1] - prefix[l]def build_prefix(arr):
prefix = [0] * (len(arr) + 1)
for i, x in enumerate(arr):
prefix[i + 1] = prefix[i] + x # running total
return prefix
def range_sum(prefix, l, r): # inclusive l..r
return prefix[r + 1] - prefix[l] # O(1)
p = build_prefix([2, 4, 1, 3, 5])
range_sum(p, 1, 3) # 4+1+3 -> 8
arr = [2, 4, 1, 3, 5]
prefix = [0, 2, 6, 7, 10, 15]
sum(1..3) = prefix[4] - prefix[1] = 10 - 2 = 8
স্থির ডেটায় অনেক range-sum queries এর জন্য আদর্শ। বৈচিত্র্য: সাবম্যাট্রিক্স সাম এর জন্য 2D prefix sums, prefix XOR, এবং range updates এর জন্য difference arrays। যদি array প্রায়শই পরিবর্তিত হয়, তার পরিবর্তে একটি Fenwick/segment tree ব্যবহার করুন। index offset দেখুন (আকার n+1)।
Prefix sums পুনরাবৃত্ত O(n) range queries কে O(1) lookups এ রূপান্তরিত করে — যখন queries ঘন ঘন থাকে তখন একটি বিশাল জয়।
এক বার পূর্বগণনা করুন, দ্রুত উত্তর দিন এই প্যাটার্ন অনেক ডেটা-প্রসেসিং কাজ এ সাধারণীকৃত করে।
এটি প্রতিযোগিতামূলক প্রোগ্রামিং এর একটি প্রধান উপাদান এবং বিশ্লেষণে একটি সাধারণ বিল্ডিং ব্লক।