Problem link ও উৎস
- **Original source:** Classic precomputation technique (running total)
- **Platform:** LeetCode Range Sum Query Immutable —
, CSES Static Range Sum Queries —
- **Topic:** Math-based programming fundamentals → Level 5: Prefix, Difference, Contribution
- **Difficulty:** Easy
- **Pattern:** running total (prefix sum build)
- **Basic idea inherited from:** — (এটাই এই level-এর শিকড়, আগে কিছু নেই)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#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` ঠিকঠাক বানানো।
### Input ও output {#6-example-input-and-output}
```text
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 বিয়োগকেও সামলায়।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো তুমি প্রতিদিন কত টাকা খরচ করলে সেটা একটা খাতায় লিখছ: সোমবার 2, মঙ্গলবার 5, বুধবার 1, বৃহস্পতিবার 3, শুক্রবার 4।
এখন প্রতিদিন শেষে তুমি আরেকটা কলামে লিখে রাখছ **"শুরু থেকে আজ পর্যন্ত মোট কত খরচ হলো"**:
- সোমবার শেষে: 2
- মঙ্গলবার শেষে: 7
- বুধবার শেষে: 8
- বৃহস্পতিবার শেষে: 11
- শুক্রবার শেষে: 15
এই "মোট কত জমল" কলামটাই prefix sum। প্রতিদিন তুমি আগের মোটের সাথে আজকেরটা যোগ করছ — পুরো সপ্তাহ আবার গোনার দরকার নেই।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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 — সেটুকু পারলেই এটা ধরা যায়।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea হলো **cumulative sum** (জমা যোগফল)। প্রতিটা position-এ "এই পর্যন্ত মোট কত জমল" সেটা ধরে রাখা।
মূল সমীকরণ একটাই:
```text
P[i + 1] = P[i] + a[i]
```
মানে নতুন total = আগের total + এখনকার element। এটা একটা **recurrence** — আগেরটার উপর ভর দিয়ে পরেরটা। এক pass-এই পুরো array তৈরি হয়ে যায়, কারণ প্রতিটা ঘর শুধু তার ঠিক আগের ঘরের উপর নির্ভর করে।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
ধরো prefix array না বানিয়ে সরাসরি "প্রতিটা i-এর জন্য প্রথম i টা element যোগ করো" করতে গেলে — প্রতিবার শুরু থেকে যোগ:
```python
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²)**।
```text
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]` যোগ করলেই হয়।
```python
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 — সব জায়গায় ফিরবে। মূল মন্ত্র: *একবার করা হিসাব দ্বিতীয়বার কোরো না।*
### ছবিতে বোঝা {#5-visual-explanation}
প্রথমে দেখো কীভাবে `P` array এক ধাপ এক ধাপ ভরে — প্রতিটা ঘর আগের ঘর + এখনকার element:
```text
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 লাগে না। এটাই জাদুর চাবি।
### ছোট input-এ ধাপে ধাপে {#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 ✓।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
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}
```text
P = [0] * (len(a) + 1)
```
`a`-র চেয়ে এক বড় একটা array বানাচ্ছি, সব 0 দিয়ে ভরা। এই বাড়তি ঘরটাই `P[0] = 0` sentinel — খালি prefix।
```text
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 একটা ঘর সরিয়ে দিয়েছে।
```text
return P
```
পুরো prefix array ফেরত।
বাকি `assert` গুলো নিজেদের চেক করছে: fast version আর slow `prefix_brute` একই উত্তর দিচ্ছে কিনা, খালি/negative edge case ঠিক আছে কিনা। সব ঠিক থাকলে শেষে `সব test pass!` ছাপে।
### Output মিলিয়ে দেখা {#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:
```text
[0, 2, 7, 8, 11, 15]
[0, 10]
সব test pass!
```
### JavaScript ও test cases {#21-javascript-solution-with-test-cases}
JS-এ length n+1-এর array বানিয়ে sentinel `P[0] = 0` রেখে running total — Python-এর হুবহু।
```javascript
// 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 একঘর সরায়)।
### TypeScript ও test cases {#22-typescript-solution-with-test-cases}
```typescript
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ड़बड় আগেই বাদ।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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}
1. **`P`-র দৈর্ঘ্য n বানানো (n+1 না)** — sentinel `P[0] = 0` বাদ পড়ে; তখন range query-তে l=0-এর জন্য আলাদা if লাগে। সবসময় n+1 ঘর রাখো।
2. **Index গুলিয়ে ফেলা** — `a[i]` যায় `P[i+1]`-এ, `P[i]`-তে না। `P[i+1] = P[i] + a[i]` মুখস্থ না করে ছবিতে মেলাও।
3. **Loop `range(len(a)+1)` চালানো** — তাহলে `a[i]` শেষে out-of-range। loop চলবে `range(len(a))`, কারণ আমরা `a`-র উপর হাঁটছি, `P`-র উপর না।
4. **খালি array ভুলে যাওয়া** — `[]`-এর prefix `[0]` (শুধু sentinel); code এটা এমনিতেই সামলায়, কিন্তু পরীক্ষা করে নাও।
5. **প্রতিবার `sum(a[:i])` করা** — দেখতে সহজ, কিন্তু এটাই গোপন O(n²)। আগের total-এ ভর করো।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **LeetCode — Range Sum Query Immutable** (