Problem link ও উৎস
- **Original source:** Classic point-update + range-sum exercise
- **Platform:** LeetCode —
- **Topic:** segment tree and fenwick tree
- **Difficulty:** Medium
- **Pattern:** segment tree / Fenwick core (point update + range sum)
- **Basic idea inherited from:** arrays, recursion
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
আবার একটা array আর `sumRange(left, right)` query — কিন্তু এবার একটা নতুন operation যোগ হয়েছে: `update(index, val)`, যা `index`-এর element-কে `val` বানিয়ে দেয়। update আর query যেকোনো order-এ, বহুবার আসতে পারে। এই একটা শব্দ — **Mutable** — পুরো খেলা বদলে দেয়।
```text
NumArray([1, 3, 5])
sumRange(0, 2) -> 1 + 3 + 5 = 9
update(1, 2) -> array এখন [1, 2, 5]
sumRange(0, 2) -> 1 + 2 + 5 = 8
```
### Input ও output {#8-example-input-and-output}
```text
NumArray([1, 3, 5])
sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8
Edge case 1 (একই value-তে update): update(0, 1) পরে sumRange(0,0) -> 1
Edge case 2 (শেষ element update): update(2, 10) পরে sumRange(0,2) -> 1+2+10 = 13
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
একটা mall-এর প্রতিটা তলায় বিক্রির running total রাখা আছে, আর প্রতিটা wing-এ wing-total, পুরো mall-এ grand total। একটা দোকানের বিক্রি বদলালে তুমি শুধু ওই দোকান → তার wing → তার তলা → grand total — এই একটা শৃঙ্খলে খবর দাও, পুরো mall নতুন করে গুনতে হয় না। আবার "এই কয়েকটা wing-এর মোট কত" জিজ্ঞেস করলে কয়েকটা wing-total জোড়া দিলেই হয়।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা **arrays আর recursion**-এর উপর দাঁড়িয়ে। কিন্তু আসলে এটা problem #1/#2-এর immutable prefix-sum baseline-এর সরাসরি উত্তরসূরি — যেখানে baseline ভেঙে পড়ে, ঠিক সেখান থেকেই এই problem শুরু।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic: prefix sums update-এর সাথে যায় না। একটা update prefix array-র পরের প্রতিটা entry stale করে দেয় ([../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/](../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/README.md)-এ দেখা গেছে) — তাই update O(n)। সমাধান: pre-computation-কে এত ছোট টুকরোয় ভাঙো যে একটা update মাত্র O(log n)-টা টুকরো invalid করে। এটাই segment tree / Fenwick-এর central tweak: **element নয়, segment-এর answer জমাও**।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
দুটো পথই খাটে: **segment tree** (range sum + point update) অথবা **Fenwick tree** (sum-এর জন্য আরও ছোট code)। যেহেতু এটা plain sum, Fenwick-ই সংক্ষিপ্ততম; কিন্তু segment tree generalize করে (min/max-এও চলে)। নিচে দুটোই দিলাম।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
Update আর query — দুটোকেই O(log n)-এ দরকার। prefix sums query-তে দ্রুত কিন্তু update-এ O(n); plain array update-এ দ্রুত কিন্তু query-তে O(n)। Tree দুই দিকেই log n দেয়, কারণ একটা leaf মাত্র O(log n)-টা segment-এর ভেতরে থাকে আর প্রতিটা query O(log n)-টা segment জুড়ে তৈরি হয়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: plain array রাখো। `update` মানে সরাসরি `a[index] = val` (O(1)); `sumRange` মানে loop চালিয়ে যোগ (O(n))।
```text
update(i, v): a[i] = v
sumRange(l, r): s = 0; for i in l..r: s += a[i]
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
plain array-তে `sumRange` প্রতিবার O(n)। উল্টোটা — prefix-sum array রাখলে `sumRange` O(1) কিন্তু `update` O(n) (পরের সব prefix stale)। দুটো operation মিশে q-বার এলে দুই ক্ষেত্রেই O(n·q)। LeetCode-এ এটা টাইম-আউট করায়। কোনো plain approach দুটোকে একসাথে দ্রুত করতে পারে না।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **একটা point update পুরো prefix structure ভাঙার দরকার নেই — শুধু কয়েকটা segment**। একটা element ঠিক O(log n)-টা segment-এর ভেতরে থাকে (tree-র প্রতি level-এ একটা)। তাই ওই কটা segment-ই repair করো, বাকি সব অক্ষত থাকে।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
Segment tree-তে: leaf set করো, ফেরার পথে প্রতিটা parent re-combine করো — O(log n)। query-তে তিন-ভাগের decision নিয়ে নামো — O(log n)। Fenwick-এ: `update` মানে delta = `val - current[index]`, তারপর lowbit hop দিয়ে covering block-গুলোয় delta যোগ; `sumRange` = `prefix(r) - prefix(l-1)`।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "update এলে সব আবার হিসাব করতে হবে" — এই ভয় থেকে সরে এসে ভাবো "answer-গুলো এমনভাবে টুকরো করে রাখব যেন একটা update মাত্র এক শৃঙ্খল টুকরোকে ছোঁয়।" Immutable baseline (#1, #2) থেকে এই একটাই বড় লাফ — আর এটাই পুরো folder-এর core।
### ছবিতে বোঝা {#7-visual-explanation}
Segment tree-তে `update(1, 2)` ঠিক একটা root-to-leaf path repair করে (array `[1, 3, 5]`):
```text
before: after update(1, 2):
[0..2]=9 [0..2]=8 <- repaired
/ \ / \
[0..1]=4 [2..2]=5 [0..1]=3 [2..2]=5
/ \ / \
[0..0]=1 [1..1]=3 [0..0]=1 [1..1]=2 <- changed leaf
path touched: [1..1] -> [0..1] -> [0..2] (3 nodes, O(log n))
সব leaf rebuild করতে হয়নি — শুধু এক শৃঙ্খল।
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`[1, 3, 5]`, Fenwick পথে, `update(1, 2)` তারপর `sumRange(0, 2)`:
1. শুরুতে Fenwick build: element (1-indexed) 1,2,3 ধরে 1,3,5।
2. `update(1, 2)` → 0-indexed 1 = 1-indexed 2। delta = `2 - 3 = -1`।
3. `add(2, -1)`: index 2 → 4 ছোঁয়, ওদের value -1 হয়।
4. `sumRange(0, 2)` → `prefix(3) - prefix(0)` = (1 + 2 + 5) - 0 = 8।
5. ✓ ঠিক `[1, 2, 5]`-এর মোট।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
class Fenwick:
"""update-সহ prefix sums, 1-indexed। sum-এর জন্য সংক্ষিপ্ততম structure।"""
def __init__(self, n):
self.n = n
self.tree = [0] * (n + 1)
def add(self, i, delta): # element i += delta (1-indexed)
while i <= self.n:
self.tree[i] += delta
i += i & (-i)
def prefix_sum(self, i): # sum of 1..i
s = 0
while i > 0:
s += self.tree[i]
i -= i & (-i)
return s
class NumArray:
"""Mutable range sum — Fenwick দিয়ে। 0-indexed API, ভেতরে 1-indexed BIT।
point update + range sum দুটোই O(log n)। (sum বলে BIT যথেষ্ট;
min/max হলে segment tree লাগত।)"""
def __init__(self, nums):
self.nums = list(nums) # set semantics-এর জন্য current value
self.fw = Fenwick(len(nums))
for i, v in enumerate(nums):
self.fw.add(i + 1, v) # build via adds
def update(self, index, val):
delta = val - self.nums[index] # set = (new - old) যোগ করা
self.nums[index] = val
self.fw.add(index + 1, delta)
def sumRange(self, left, right): # 0-indexed inclusive
return self.fw.prefix_sum(right + 1) - self.fw.prefix_sum(left)
def brute(arr, l, r):
return sum(arr[l:r + 1])
# ---- tests ----
na = NumArray([1, 3, 5])
assert na.sumRange(0, 2) == 9
na.update(1, 2)
assert na.sumRange(0, 2) == 8 # [1, 2, 5]
na.update(2, 10)
assert na.sumRange(0, 2) == 13 # [1, 2, 10]
# update আর query মিশিয়ে, একটা mirror array-র সাথে exhaustively মেলানো
import random
random.seed(7)
arr = [random.randint(-5, 5) for _ in range(12)]
na = NumArray(arr)
for _ in range(300):
if random.random() < 0.5: # random update
i = random.randrange(len(arr))
v = random.randint(-5, 5)
arr[i] = v
na.update(i, v)
else: # random range query, brute-checked
l = random.randrange(len(arr))
r = random.randrange(l, len(arr))
assert na.sumRange(l, r) == brute(arr, l, r)
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `self.nums = list(nums)` — set semantics-এর জন্য current value মনে রাখি, যাতে delta বের করা যায়।
- `update`: `delta = val - old`; BIT শুধু "যোগ" বোঝে, তাই set করতে delta যোগ করি।
- `sumRange`: `prefix(right+1) - prefix(left)` — 0-indexed inclusive থেকে 1-indexed prefix-এ রূপান্তর।
- `brute` + random fuzz — update/query মিশিয়ে একটা সরল mirror array-র সাথে মিলিয়ে দেখা।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`NumArray([1,3,5])`: `sumRange(0,2)=9`। `update(1,2)` delta `-1` ঠেলে; `sumRange(0,2)=8`। `update(2,10)` পরে `13`। তারপর 300 random op-এর fuzz: প্রতিটা query mirror array-র brute sum-এর সাথে মেলে। সব assert pass। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**update O(log n)**, **sumRange O(log n)** (দুটো prefix call)। Build O(n log n) (n বার add)।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(n)** — Fenwick array + current-value array।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- `update`-এ delta-র বদলে সরাসরি `val` add করা — তখন পুরোনো value যোগ থেকে যায়, ভুল।
- 0-indexed/1-indexed গুলিয়ে ফেলা — `sumRange`-এ `right+1` আর `prefix_sum(left)` দরকার।
- Mutable জেনেও plain prefix-sum array ব্যবহার করা — update-এ O(n), টাইম-আউট।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: arrays + recursion, আর সরাসরি #1/#2-এর immutable baseline ([../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/](../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/README.md))। তফাত একটাই: update যোগ হওয়ায় baseline ভেঙে পড়েছে। গভীর: [../segment-tree.md](../segment-tree.md), [../fenwick-tree.md](../fenwick-tree.md), [../implementation.py](../implementation.py)।
### পরের অনুশীলন {#22-similar-harder-problems}
- Dynamic Range Sum Queries (একই, contest version) —