![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/fjij1x98sg6j8e9satkd.jpg) Prefix Sum হল Ad-hoc problem এর Tecnique. Ad-hoc: An Ad-hoc Problem is a Problem that doesn't have a Standard algorithm or Technique to Solve. Prefix Sum : ধরেন আপনাকে একটি প্রোগ্রাম লিখতে বলা হল যেখানে একটি array [a1, a2, a3, ...] দেওয়া হল এবং একটি q দেওয়া হল querie করার জন্য এবং প্রতিটি querie তে একাধিক (l, r) প্রশ্নের উত্তর দিতে হবে। এই প্রবলেম এর সবচেয়ে সহজ সমাধান হল আমাকে যেই range (l, r) দেওয়া আছে সেই range এর l থেকে r পর্যন্ত loop চালালে সমাধান পেয়ে যাব কিন্তু যদি querie সংখা অনেক বেশি হয় তা হলে এর Time Complexity অনেক বেশি হয়ে যাবে। আমরা যদি Prefix Sum Technique এই প্রবলেমটা সল্ভ করি তা হলে O(Q+n) এ সল্ভ করতে পারি। Array n = 4 index : 0 1 2 3 value : 1 2 3 4 prefix : 1 3 6 10 ``` range: l r = prefix[r] - prefix[l-1] 1 3 = 10 - 1 = 9 ``` ``` Algorithm: Read the Array Size n: Initialize an array arr of size n. Input the Elements into arr: For each i from 0 to n-1, input the value of arr[i]. Construct the Prefix Sum Array pre: Initialize pre of size n. Set pre[0] = arr[0] (the first element). For each index i from 1 to n-1, calculate: pre[i] = pre[i-1] + arr[i] This step ensures that pre[i] holds the sum of all elements from arr[0] to arr[i]. Process Each Query: Read the integer q (number of queries). For each query: Input the range [l, r] (0-indexed). If l == 0, print pre[r] (sum from start to r). Else, print pre[r] - pre[l - 1] (sum from index l to r). ``` Code in C++ ``` #include using namespace std; int main() { int n; cin >> n; int arr[n+1]; // input array for(int i=0; i> arr[i]; // apply prefix int pre[n+1]; pre[0] = arr[0]; for(int i=1; i> q; while(q--) { int l, r; cin >> l >> r; if(l == 0)cout << pre[r] << endl; else cout << pre[r] - pre[l - 1] << endl; } } ``` Practise Problems: 1. [CSUMQ - Cumulative Sum Query](https://www.spoj.com/problems/CSUMQ/) 2. [108 - Maximum Sum](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=44) 3. [983 - Localized Summing for Blurring](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=924) 4. [11951 - Area](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3102)

alamin_cse97

1-D Prefix Sum

Join Our Newsletter. No Spam, Only the good stuff.