067 — Prefix Sum¶

এই note দিয়ে Level 5-এর যাত্রা শুরু — অভিনন্দন! এই একটা idea, prefix sum, পুরো level-এর শিকড়; 068 থেকে 080 পর্যন্ত প্রায় সবাই এটার কাঁধে দাঁড়াবে। দোকানদার যেমন প্রতিবার খাতা না গুনে একটা running total রাখে, আমরাও তাই করব। ধীরে পড়ো, ফিতার ছবিটা মনে গেঁথে নাও — তাড়া নেই।

Source¶

Original source: Classic precomputation technique (running total)
Platform: LeetCode Range Sum Query Immutable — https://leetcode.com/problems/range-sum-query-immutable/, CSES Static Range Sum Queries — https://cses.fi/problemset/task/1646
Topic: Math-based programming fundamentals → Level 5: Prefix, Difference, Contribution
Difficulty: Easy
Pattern: running total (prefix sum build)
Basic idea inherited from: — (এটাই এই level-এর শিকড়, আগে কিছু নেই)

1. Problem in simple words¶

একটা সংখ্যার array a দেওয়া আছে। তোমার কাজ হলো একটা নতুন array P বানানো যেখানে P[i] মানে "শুরু থেকে প্রথম i টা element-এর মোট যোগফল"।

মানে:

P[0] = 0 (কিছুই যোগ করিনি)
P[1] = a[0]
P[2] = a[0] + a[1]
... এভাবে চলতে থাকবে।

এই P array-টাই হলো prefix sum array। একবার বানিয়ে নিলে, পরে যেকোনো range-এর sum চোখের পলকে বের করা যায় (সেটা 068-এ শিখব)। আজকের target শুধু P ঠিকঠাক বানানো।

2. What is the math idea?¶

মূল idea হলো cumulative sum (জমা যোগফল)। প্রতিটা position-এ "এই পর্যন্ত মোট কত জমল" সেটা ধরে রাখা।

মূল সমীকরণ একটাই:

P[i + 1] = P[i] + a[i]

মানে নতুন total = আগের total + এখনকার element। এটা একটা recurrence — আগেরটার উপর ভর দিয়ে পরেরটা। এক pass-এই পুরো array তৈরি হয়ে যায়, কারণ প্রতিটা ঘর শুধু তার ঠিক আগের ঘরের উপর নির্ভর করে।

3. Which basic idea does this inherit from?¶

এটা Level 5-এর প্রথম problem, তাই এর নিচে দাঁড়ানোর মতো আগের prefix-problem নেই (তাই "inherited from: —")।

বরং এটাই সেই বীজ যেখান থেকে পুরো level গজাবে:

068 (Range Sum Query) — এই P দিয়ে P[r+1] - P[l] করে range sum
069 (Difference Array) — এটার ঠিক উল্টো অপারেশন
071 (Prefix XOR) — যোগের জায়গায় XOR বসিয়ে একই template
073 (Subarray Sum = K) — P + hash map

মূল ভিত্তি Level 0-এর simple loop আর array indexing — সেটুকু পারলেই এটা ধরা যায়।

4. Real-life analogy¶

ভাবো তুমি প্রতিদিন কত টাকা খরচ করলে সেটা একটা খাতায় লিখছ: সোমবার 2, মঙ্গলবার 5, বুধবার 1, বৃহস্পতিবার 3, শুক্রবার 4।

এখন প্রতিদিন শেষে তুমি আরেকটা কলামে লিখে রাখছ "শুরু থেকে আজ পর্যন্ত মোট কত খরচ হলো":

সোমবার শেষে: 2
মঙ্গলবার শেষে: 7
বুধবার শেষে: 8
বৃহস্পতিবার শেষে: 11
শুক্রবার শেষে: 15

এই "মোট কত জমল" কলামটাই prefix sum। প্রতিদিন তুমি আগের মোটের সাথে আজকেরটা যোগ করছ — পুরো সপ্তাহ আবার গোনার দরকার নেই।

5. Visual explanation¶

প্রথমে দেখো কীভাবে P array এক ধাপ এক ধাপ ভরে — প্রতিটা ঘর আগের ঘর + এখনকার element:

a   =   [ 2 ]  [ 5 ]  [ 1 ]  [ 3 ]  [ 4 ]
index     0      1      2      3      4

P[0] = 0  (sentinel — খালি দিয়ে শুরু)
P[1] = P[0] + a[0] = 0 + 2 = 2
P[2] = P[1] + a[1] = 2 + 5 = 7
P[3] = P[2] + a[2] = 7 + 1 = 8
P[4] = P[3] + a[3] = 8 + 3 = 11
P[5] = P[4] + a[4] = 11 + 4 = 15

P   =   [ 0 ]  [ 2 ]  [ 7 ]  [ 8 ]  [ 11 ]  [ 15 ]
index     0      1      2      3       4       5

লক্ষ করো — P-র দৈর্ঘ্য a-র চেয়ে এক বেশি (n+1)। প্রথম ঘর P[0] = 0 হলো sentinel (পাহারাদার): এটা থাকলে পরে range query-র formula সব জায়গায় একরকম হয়, l=0-এর জন্য আলাদা if লাগে না। এটাই জাদুর চাবি।

6. Example input and output¶

input  a              ->  output P
-------------------------------------------------
[2, 5, 1, 3, 4]       ->  [0, 2, 7, 8, 11, 15]
[10]                  ->  [0, 10]
[]                    ->  [0]              (খালি array, শুধু sentinel)
[-1, 2, -3]           ->  [0, -1, 1, -2]   (negative-ও ঠিক চলে)
[5, 5, 5]             ->  [0, 5, 10, 15]

Edge case খেয়াল করো: খালি array দিলেও P = [0] (শুধু sentinel)। আর negative সংখ্যাতেও যোগ একইভাবে কাজ করে — prefix sum বিয়োগকেও সামলায়।

7. Brute force thinking¶

ধরো prefix array না বানিয়ে সরাসরি "প্রতিটা i-এর জন্য প্রথম i টা element যোগ করো" করতে গেলে — প্রতিবার শুরু থেকে যোগ:

def prefix_brute(a):
    n = len(a)
    P = [0] * (n + 1)
    for i in range(n + 1):
        total = 0
        for j in range(i):       # প্রতিবার শুরু থেকে আবার যোগ
            total += a[j]
        P[i] = total
    return P

এটা ঠিক উত্তরই দেয় — প্রতি ঘরের জন্য আবার গোড়া থেকে যোগ করে।

8. Why brute force may be slow¶

সমস্যা হলো ভেতরের loop। P[i] বের করতে i টা যোগ লাগছে, তাই মোট কাজ 0 + 1 + 2 + ... + n ≈ n²/2। এটা O(n²)।

n = 100000 হলে:
  brute force: ~5,000,000,000 operation  (ধীর, O(n²)) — TLE
  smart way  : ~100,000 operation        (এক pass, O(n))

মূল অপচয়টা চোখে পড়ছে? P[3] বের করতে গিয়ে আমি a[0]+a[1]+a[2] যোগ করলাম, আবার P[4]-এ a[0]+a[1]+a[2]+a[3] — মানে a[0]+a[1]+a[2] অংশটা আবার যোগ করলাম। একই হিসাব বারবার!

9. Better thinking¶

মূল insight: P[i+1] বের করতে গোড়া থেকে যোগ করার দরকার নেই — আগের total P[i] তো হাতেই আছে, শুধু তার সাথে a[i] যোগ করলেই হয়।

def prefix_sum(a):
    P = [0] * (len(a) + 1)
    for i in range(len(a)):
        P[i + 1] = P[i] + a[i]
    return P

এখন প্রতিটা ঘর মাত্র একটা যোগ — মোট n টা যোগ, তাই O(n)। আগের কাজ ফেলে দিচ্ছি না, ভর করছি।

10. Thinking tweak¶

আসল "আহা!" মুহূর্ত: আগের উত্তরটা ফেলে দিও না — তার উপর দাঁড়াও। P[i] ইতিমধ্যে "প্রথম i টার মোট" জানে, তাই পরের মোট পেতে শুধু একটা নতুন element যোগ করলেই চলে।

এই "পুরোটা আবার না করে আগেরটায় একটু যোগ করা" চিন্তাটাই হলো prefix কৌশলের হৃদয়। একই চিন্তা পরে difference array, sliding window — সব জায়গায় ফিরবে। মূল মন্ত্র: একবার করা হিসাব দ্বিতীয়বার কোরো না।

11. Step-by-step dry run¶

চলো a = [2, 5, 1, 3] ধীরে চালাই। শুরুতে P = [0, 0, 0, 0, 0] (দৈর্ঘ্য 5):

i	a[i]	P[i] (আগের total)	P[i+1] = P[i] + a[i]	P এখন
0	2	0	0 + 2 = 2	[0, 2, 0, 0, 0]
1	5	2	2 + 5 = 7	[0, 2, 7, 0, 0]
2	1	7	7 + 1 = 8	[0, 2, 7, 8, 0]
3	3	8	8 + 3 = 11	[0, 2, 7, 8, 11]

শেষ অবস্থা: P = [0, 2, 7, 8, 11]। প্রতিটা ঘর তার আগের ঘরের উপর দাঁড়িয়ে একটা মাত্র যোগে তৈরি হলো। মিলিয়ে নাও: P[3] = 8 মানে প্রথম 3টা (2+5+1) = 8 ✓।

12. Python solution¶

def prefix_sum(a):
    """a-র prefix sum array P ফেরত দেয়; P[i] = প্রথম i টা element-এর মোট।
    P-র দৈর্ঘ্য len(a) + 1, আর P[0] = 0 (sentinel)।"""
    P = [0] * (len(a) + 1)
    for i in range(len(a)):
        P[i + 1] = P[i] + a[i]
    return P


def prefix_brute(a):
    """ধীর O(n^2) version — শুধু মিলিয়ে দেখার জন্য (প্রতিবার গোড়া থেকে যোগ)।"""
    n = len(a)
    P = [0] * (n + 1)
    for i in range(n + 1):
        P[i] = sum(a[:i])
    return P


# --- ছোট test গুলো (সব pass করা উচিত) ---
assert prefix_sum([2, 5, 1, 3, 4]) == [0, 2, 7, 8, 11, 15]
assert prefix_sum([10]) == [0, 10]
assert prefix_sum([]) == [0]                 # খালি array → শুধু sentinel
assert prefix_sum([-1, 2, -3]) == [0, -1, 1, -2]   # negative-ও ঠিক
assert prefix_sum([5, 5, 5]) == [0, 5, 10, 15]

# fast আর brute একই উত্তর দেয় কিনা (brute-force cross-check):
for arr in ([2, 5, 1, 3, 4], [], [10], [-1, 2, -3], [0, 0, 7]):
    assert prefix_sum(arr) == prefix_brute(arr)

# একটা ধর্ম: শেষ ঘর = পুরো array-র মোট
assert prefix_sum([2, 5, 1, 3, 4])[-1] == sum([2, 5, 1, 3, 4])

print(prefix_sum([2, 5, 1, 3, 4]))   # [0, 2, 7, 8, 11, 15]
print(prefix_sum([10]))              # [0, 10]
print("সব test pass!")

13. Line-by-line explanation¶

P = [0] * (len(a) + 1)

a-র চেয়ে এক বড় একটা array বানাচ্ছি, সব 0 দিয়ে ভরা। এই বাড়তি ঘরটাই P[0] = 0 sentinel — খালি prefix।

for i in range(len(a)):
    P[i + 1] = P[i] + a[i]

প্রতিটা element-এর উপর একবার হাঁটছি। নতুন total P[i+1] = আগের total P[i] + এখনকার element a[i]। লক্ষ করো index — a-র i-তম element যাচ্ছে P-র (i+1)-তম ঘরে, কারণ sentinel একটা ঘর সরিয়ে দিয়েছে।

return P

পুরো prefix array ফেরত।

বাকি assert গুলো নিজেদের চেক করছে: fast version আর slow prefix_brute একই উত্তর দিচ্ছে কিনা, খালি/negative edge case ঠিক আছে কিনা। সব ঠিক থাকলে শেষে সব test pass! ছাপে।

14. Output walkthrough¶

a = [2, 5, 1, 3, 4] চালালে:

প্রথম print → section 11-এর dry run-এর মতো ঘর ভরে ভরে → [0, 2, 7, 8, 11, 15]
দ্বিতীয় print → [10]-এর জন্য [0, 10]
সব assert চুপচাপ pass (assert fail না করলে কিছু ছাপে না)
শেষে সব test pass!

ছাপা output:

[0, 2, 7, 8, 11, 15]
[0, 10]
সব test pass!

15. Time complexity¶

O(n) — array-র প্রতিটা element-এ ঠিক একবার হাঁটছি, প্রতি ধাপে একটা যোগ আর একটা assignment। n element মানে n ধাপ। brute force-এর O(n²) থেকে এটা বিশাল উন্নতি।

16. Space complexity¶

O(n) — n+1 দৈর্ঘ্যের নতুন একটা array P রাখছি। input ছাড়া এটুকুই বাড়তি জায়গা। (চাইলে a-কেই in-place prefix বানিয়ে O(1) extra করা যায়, কিন্তু আলাদা P রাখা পরিষ্কার আর নিরাপদ।)

17. Common mistakes¶

P-র দৈর্ঘ্য n বানানো (n+1 না) — sentinel P[0] = 0 বাদ পড়ে; তখন range query-তে l=0-এর জন্য আলাদা if লাগে। সবসময় n+1 ঘর রাখো।
Index গুলিয়ে ফেলা — a[i] যায় P[i+1]-এ, P[i]-তে না। P[i+1] = P[i] + a[i] মুখস্থ না করে ছবিতে মেলাও।
Loop range(len(a)+1) চালানো — তাহলে a[i] শেষে out-of-range। loop চলবে range(len(a)), কারণ আমরা a-র উপর হাঁটছি, P-র উপর না।
খালি array ভুলে যাওয়া — []-এর prefix [0] (শুধু sentinel); code এটা এমনিতেই সামলায়, কিন্তু পরীক্ষা করে নাও।
প্রতিবার sum(a[:i]) করা — দেখতে সহজ, কিন্তু এটাই গোপন O(n²)। আগের total-এ ভর করো।

18. Harder problems that inherit this idea¶

LeetCode — Range Sum Query Immutable (https://leetcode.com/problems/range-sum-query-immutable/) — এই prefix array দিয়েই query-র উত্তর; ঠিক পরের ধাপ (068)।
CSES — Static Range Sum Queries (https://cses.fi/problemset/task/1646) — একই prefix, অনেক query।
LeetCode — Subarray Sum Equals K (https://leetcode.com/problems/subarray-sum-equals-k/) — prefix + hash map (073)।

19. Pattern learned¶

Prefix sum build (running total) — P[i+1] = P[i] + a[i] দিয়ে এক pass-এ cumulative sum। বড় শিক্ষা: আগের হিসাবের উপর ভর করো, পুরোটা আবার গুনো না। এই precompute-চিন্তাই পুরো Level 5-এর ভিত্তি।

20. Final summary¶

ভবিষ্যতের আমাকে এক লাইনে: "prefix sum = running total; P[i+1] = P[i] + a[i], P[0] = 0 sentinel রাখো (দৈর্ঘ্য n+1)। একবার বানিয়ে রাখলে range query চোখের পলকে — এটাই Level 5-এর শিকড়।"

পরের ধাপ → 068 — Range Sum Query (এই P দিয়ে P[r+1] - P[l] করে range-এর sum)।

ফিরে দেখা: এই level-এর map → ../README.md · concept ঝালাই → ../concept-notes.md · এই note-টা যে ছকে লেখা → ../../../templates/math-problem-note-template.md।

21. JavaScript solution (with test cases)¶

JS-এ length n+1-এর array বানিয়ে sentinel P[0] = 0 রেখে running total — Python-এর হুবহু।

// throwing assert — fail করলে থেমে error দেবে
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };

function prefixSum(a) {
  const P = new Array(a.length + 1).fill(0);   // n+1 ঘর, P[0]=0 sentinel
  for (let i = 0; i < a.length; i++) {
    P[i + 1] = P[i] + a[i];                     // আগের total + এখনকার element
  }
  return P;
}

// ---- test cases (file-এর example + edge case) ----
const eq = (x, y) => JSON.stringify(x) === JSON.stringify(y);
assert(eq(prefixSum([2, 5, 1, 3, 4]), [0, 2, 7, 8, 11, 15]), "basic");
assert(eq(prefixSum([10]), [0, 10]), "single");
assert(eq(prefixSum([]), [0]), "খালি → শুধু sentinel");
assert(eq(prefixSum([-1, 2, -3]), [0, -1, 1, -2]), "negative");
assert(eq(prefixSum([5, 5, 5]), [0, 5, 10, 15]), "5,5,5");
// ধর্ম: শেষ ঘর = পুরো array-র মোট
const arr = [2, 5, 1, 3, 4];
assert(prefixSum(arr)[arr.length] === arr.reduce((s, v) => s + v, 0), "last = total");
console.log("সব JS test pass!");

JS টীকা: new Array(n + 1) করলে ঘরগুলো empty থাকে — .fill(0) না দিলে P[i] + a[i] প্রথম ঘরে undefined + x = NaN দেবে; তাই .fill(0) জরুরি। index মনে রাখো — a[i] যায় P[i + 1]-এ (sentinel একঘর সরায়)।

22. TypeScript solution (with test cases)¶

function prefixSum(a: number[]): number[] {
  const P: number[] = new Array(a.length + 1).fill(0);
  for (let i = 0; i < a.length; i++) P[i + 1] = P[i] + a[i];
  return P;
}

function expectArr(actual: number[], expected: number[], msg = ""): void {
  if (JSON.stringify(actual) !== JSON.stringify(expected)) {
    throw new Error(`FAIL ${msg}: [${actual}]`);
  }
}

expectArr(prefixSum([2, 5, 1, 3, 4]), [0, 2, 7, 8, 11, 15], "basic");
expectArr(prefixSum([]), [0], "খালি");
expectArr(prefixSum([-1, 2, -3]), [0, -1, 1, -2], "negative");
console.log("সব TS test pass!");

TS টীকা: input ও output number[] declare করায় ভুলে string[] পাঠানো বা mixed array return করা compile-time-এ আটকায় — prefix-এর index/value gड़बड় আগেই বাদ।

23. কোথায় কাজে লাগে (real-world use)¶

Range sum query: একবার prefix বানিয়ে যেকোনো range-এর sum P[r+1] - P[l]-এ O(1) — analytics dashboard, time-series-এ নিত্য।
Cumulative metrics: running total, cumulative revenue/visitor count, progress bar — সবই prefix sum।
2D image / heatmap (integral image): এই idea দুই মাত্রায় গেলে যেকোনো rectangle-এর sum O(1) — computer vision, blur, box filter।
Probability / weighted sampling: cumulative distribution বানিয়ে binary search দিয়ে দ্রুত random pick। মূল pattern — "আগের হিসাবের উপর ভর করো, পুরোটা আবার গুনো না (precompute)" — caching, dynamic programming, difference array জুড়ে বড় ছবিতে ফেরে।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখো; problem statement copy কোরো না; official link শুধু attribution-এর জন্য রাখো; "asked by Google/Amazon" এমন দাবি কোরো না — বরং "Google-style pattern" / "common interview pattern" লেখো।