আগে একবার পুরো list দেখে রাখুন, তাহলে পরের প্রতিটা প্রশ্নের উত্তর হবে মাত্র একটা subtraction।
ভাবুন একটা bank statement, যেখানে প্রতিটা transaction-এর পর running balance লেখা আছে। 3 নম্বর থেকে 6 নম্বর transaction-এর মধ্যে কত খরচ হয়েছে? খরচগুলো আবার যোগ করতে হবে না: 6 নম্বরের পরের balance থেকে 3 নম্বরের আগের balance বিয়োগ করলেই হবে।
একটা prefix sum array p হলো ঠিক সেই running balance: p[i] হলো প্রথম iটা সংখ্যার যোগফল। তখন nums[l..r]-এর যোগফল হয় p[r+1] − p[l]। আমরা একটা বাড়তি slot p[0] = 0 রাখি (কিছু না থাকলে যোগফল 0), যাতে l 0 হলেও formula কাজ করে।
l = 0, r = 0। prefix-এর কোন দুটো cell ব্যবহার হয়, আর p[0] = 0 কেন দরকার?l = 0, r = শেষ index)। prefix-এর কোন একটা cell-এ মোট যোগফল থাকে?5, -2, 7)। পদ্ধতিটা তবুও কাজ করে। কেন?p[0] = 0 না থাকলে index 0 থেকে শুরু হওয়া range-এর জন্য আলাদা special case লাগে।[l, r]-এর formula হলো p[r+1] - p[l], p[r] - p[l] নয়।Build: O(n) time একবারই লাগে। প্রতিটা query: O(1)। Space: prefix array-র জন্য O(n)। এটা না থাকলে প্রতিটা query-তে n পর্যন্ত সংখ্যা আবার যোগ করতে হতো (প্রতিটায় O(n))।