Problem link ও উৎস
- **Original source:** Classic prefix-sum exercise (class-based API)
- **Platform:** LeetCode —
- **Topic:** segment tree and fenwick tree (baseline — tree লাগে না)
- **Difficulty:** Easy
- **Pattern:** prefix sums baseline, একটা reusable class-এ মোড়া
- **Basic idea inherited from:** math level 5 prefix sums — [../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/](../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/README.md)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে একটা integer array দেওয়া হবে একবার, constructor-এ। তারপর বারবার `sumRange(left, right)` call আসবে, প্রতিবার তোমাকে `left` থেকে `right` (দুই প্রান্ত সহ) sum return করতে হবে। array কখনো বদলায় না — তাই নাম **Immutable**। আগের problem-এর সাথে পার্থক্য শুধু একটাই: এবার এটা একটা **class-based API**, free function নয়।
```text
NumArray([-2, 0, 3, -5, 2, -1])
sumRange(0, 2) -> -2 + 0 + 3 = 1
sumRange(2, 5) -> 3 + (-5) + 2 + -1 = -1
sumRange(0, 5) -> সব মিলে = -3
```
### Input ও output {#8-example-input-and-output}
```text
NumArray([-2, 0, 3, -5, 2, -1])
sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3
Edge case 1 (একটা element): sumRange(3, 3) -> -5
Edge case 2 (পুরো শেষ অংশ): sumRange(4, 5) -> 2 + (-1) = 1
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো তুমি একটা বইয়ের প্রতিটা chapter শেষে "এ পর্যন্ত মোট কত পৃষ্ঠা পড়লে" লিখে রেখেছ। বইটা আর বদলাবে না (immutable)। এবার যে-ই জিজ্ঞেস করুক "chapter 3 থেকে 7 পর্যন্ত কত পৃষ্ঠা", তুমি শুধু "chapter 7-এর শেষে মোট" থেকে "chapter 2-এর শেষে মোট" বিয়োগ করো — পৃষ্ঠা আবার গুনতে হয় না।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটাও সরাসরি **prefix sums** ([../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/](../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/README.md))। একদম problem #1-এর মতোই — শুধু এখানে data একবার দিয়ে রাখা হয় constructor-এ, আর query method হিসেবে আসে। চিন্তা এক, মোড়ক আলাদা।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
একই invertibility: sum-কে বিয়োগ দিয়ে undo করা যায়। `P[i]` যদি প্রথম `i`-টা element-এর মোট হয়, তাহলে `sumRange(left, right) = P[right+1] - P[left]`। এখানে negative সংখ্যাও আছে, কিন্তু তাতে কিছু যায় আসে না — যোগ-বিয়োগ negative-এও দিব্যি কাজ করে।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
constructor-এ একবার বানানো একটা **prefix-sum array**, class-এর ভেতরে রাখা। তারপর প্রতিটা `sumRange` সেই array থেকে দুটো মান পড়ে বিয়োগ করে।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
API-টা স্পষ্টভাবে বলে দেয় data immutable — কোনো update method নেই। তাই segment tree বা Fenwick tree বানানো নিছক অপচয়। "Constructor-এ একবার pre-compute, তারপর O(1) query" — এটাই এই shape-এর জন্য নিখুঁত ফিট, আর ঠিক prefix sums যা করার জন্য বানানো।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: prefix কিছু না বানিয়ে, প্রতিটা `sumRange`-এ `left` থেকে `right` loop চালিয়ে যোগ করো।
```text
def sumRange(left, right):
s = 0
for i in range(left, right + 1):
s += nums[i]
return s
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
প্রতিটা `sumRange` call সর্বোচ্চ `n`-টা element ছোঁয়। যদি `q`-টা call আসে, মোট খরচ **O(n × q)**। LeetCode-এ এই call বহুবার আসে বলেই এটা টাইম-আউট ঝুঁকিতে ফেলে। একই range বারবার যোগ করাটা স্পষ্ট অপচয় — যখন একবার pre-compute করেই কাজ চলে।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: data immutable, তাই **constructor-এ একবার কাজ করে নিলে** প্রতিটা query সস্তা হয়ে যায়। `sumRange(left, right) = P[right+1] - P[left]` — দুটো array-পড়া আর একটা বিয়োগ, ব্যস।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
Constructor-এ O(n)-এ prefix array বানাও। তারপর প্রতিটা `sumRange` O(1)। অনেকগুলো query থাকলেও total খরচ build + queries = O(n + q)। Immutability-ই আমাদের এই pre-computation নিরাপদে cache করতে দেয় — কারণ কখনো invalid হওয়ার ভয় নেই।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "প্রতিবার যোগ করব" থেকে সরে এসে ভাবো "constructor-এ একবার সব checkpoint বসিয়ে দেব, query শুধু দুই checkpoint-এর তফাত পড়বে।" খেয়াল করো — এই immutability ভেঙে যদি update যোগ হতো (#5, #6), prefix array আর চলত না, তখনই segment tree / Fenwick tree-র দরকার পড়ত।
### ছবিতে বোঝা {#7-visual-explanation}
`nums = [-2, 0, 3, -5, 2, -1]`-এর prefix array `P` (sentinel `P[0]=0`):
```text
index : 0 1 2 3 4 5 6
nums : -2 0 3 -5 2 -1
P : 0 -2 -2 1 -4 -2 -3
running total (negative-এও ঠিক কাজ করে)
sumRange(2, 5):
P = [0, -2, -2, 1, -4, -2, -3]
^cut P[2] ^take P[6]
= P[right+1] - P[left] = P[6] - P[2] = -3 - (-2) = -1
(= 3 + (-5) + 2 + (-1), correct)
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`nums = [-2, 0, 3, -5, 2, -1]`, call `sumRange(2, 5)`:
1. Constructor prefix বানায়: `P = [0, -2, -2, 1, -4, -2, -3]`
2. `sumRange(2, 5)` এসেছে।
3. `P[right+1] = P[6] = -3`
4. `P[left] = P[2] = -2`
5. উত্তর = `-3 - (-2) = -1` → এটাই `3 + (-5) + 2 + (-1)`, ঠিক আছে।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
class NumArray:
"""Immutable array-র উপর O(1) range sum।
Constructor-এ একবার prefix sums বানিয়ে রাখি; কোনো update নেই
বলে tree লাগে না — এটাই দ্রুততম আর সরলতম।"""
def __init__(self, nums):
# P[i] = প্রথম i-টা element-এর sum; P[0] = 0 sentinel
self.P = [0] * (len(nums) + 1)
for i, v in enumerate(nums):
self.P[i + 1] = self.P[i] + v
def sumRange(self, left, right):
# 0-indexed inclusive [left, right] (LeetCode convention)
return self.P[right + 1] - self.P[left]
def brute(nums, left, right):
# 0-indexed inclusive, obviously-correct reference
return sum(nums[left:right + 1])
# ---- tests ----
nums = [-2, 0, 3, -5, 2, -1]
na = NumArray(nums)
assert na.sumRange(0, 2) == 1 # -2 + 0 + 3
assert na.sumRange(2, 5) == -1 # 3 - 5 + 2 - 1
assert na.sumRange(0, 5) == -3 # পুরো array
assert na.sumRange(3, 3) == -5 # একটা element
# brute force-এর সাথে exhaustively মিলিয়ে দেখা (negative-সহ array)
for left in range(len(nums)):
for right in range(left, len(nums)):
assert na.sumRange(left, right) == brute(nums, left, right)
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `self.P = [0] * (len(nums) + 1)` — n+1 ঘর, `P[0]=0` sentinel যাতে `left=0`-এও `P[left]` ঠিক থাকে।
- `self.P[i + 1] = self.P[i] + v` — running total, negative value-তেও স্বাভাবিকভাবে কাজ করে।
- `sumRange(left, right)` — `P[right+1] - P[left]`; LeetCode 0-indexed inclusive বলে `right+1`।
- `brute` — slow কিন্তু স্পষ্টভাবে সঠিক, fast version-কে verify করার জন্য।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`NumArray([-2,0,3,-5,2,-1])` বানায় `P = [0,-2,-2,1,-4,-2,-3]`। `sumRange(0,2)` দেয় `P[3]-P[0]=1`, `sumRange(2,5)` দেয় `P[6]-P[2]=-1` — সব assert pass। double loop সব `(left,right)`-কে brute-এর সাথে মেলায়। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**Constructor O(n)** (একবার prefix), **প্রতি `sumRange` O(1)**। মোট O(n + q)।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(n)** — class-এর ভেতরে রাখা n+1 ঘরের prefix array।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- `P[right] - P[left]` লেখা — `right+1` দরকার, নাহলে `right` নম্বর element বাদ যায়।
- প্রতিটা `sumRange`-এ নতুন করে prefix বানানো — তাহলে আর O(1) থাকে না, constructor-এই একবার বানাতে হয়।
- Immutable জেনেও segment tree বানানো — অপ্রয়োজনীয়; update না থাকলে prefix sums-ই যথেষ্ট।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: math level 5-এর prefix sums ([../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/](../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/README.md))। problem #1-এর সাথে যমজ — শুধু class-এর মোড়কে।
### পরের অনুশীলন {#22-similar-harder-problems}
- Static Range Sum Queries (একই idea, contest free-function style) —