Problem link ও উৎস
- **Original source:** self-exercise (এই folder-এর `segment-tree.md`-এর array-টা)
- **Platform:** self-exercise — কোনো judge নেই, ইচ্ছে করেই
- **Topic:** segment tree and fenwick tree
- **Difficulty:** Easy
- **Pattern:** build + query tracing (হাতে tree আঁকা, কাগজে উত্তর বের করা)
- **Basic idea inherited from:** recursion, divide and conquer
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
এটা judge problem নয় — একটা **hand-tracing exercise**। তোমার কাজ: array `[2, 5, 1, 4, 9, 3]`-এর জন্য একটা sum segment tree **কাগজে** আঁকো। প্রতিটা node-এ থাকবে একটা segment আর তার sum। তারপর তিনটা query-র উত্তর **হাতে** বের করো:
```text
array index: 0 1 2 3 4 5
array value: 2 5 1 4 9 3
query(1, 4) = ? query(0, 2) = ? query(3, 5) = ?
```
এরপর নিচের Python দিয়ে নিজের হাতের উত্তর মিলিয়ে নাও।
### Input ও output {#8-example-input-and-output}
```text
array = [2, 5, 1, 4, 9, 3]
query(1, 4) = 5 + 1 + 4 + 9 = 19
query(0, 2) = 2 + 5 + 1 = 8
query(3, 5) = 4 + 9 + 3 = 16
(query(0,2) আর query(3,5) ঠিক একটা করে ready node-এই বসে গেছে — দেখো tree-তে!)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
একটা company-র org chart ভাবো। প্রতিটা কর্মী (leaf) নিজের একটা সংখ্যা ধরে আছে। প্রতিটা manager (internal node) তার সরাসরি অধীনস্থদের মোট রাখে, আর CEO (root) পুরো company-র মোট। কেউ যদি জিজ্ঞেস করে "এই কটা team-এর মোট কত", তুমি কয়েকজন manager-এর কাছ থেকে ready মোট নিয়েই উত্তর দিয়ে দাও — প্রতিটা কর্মীকে আলাদা করে জিজ্ঞেস করতে হয় না।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা **recursion আর divide and conquer**-এর উপর দাঁড়িয়ে। Segment tree বানানো মানে একটা range-কে বারবার অর্ধেক করা — ঠিক merge sort যেভাবে array অর্ধেক করে। প্রতিটা node তার দুই অর্ধেকের উত্তর combine করে নিজের উত্তর বানায়।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic হলো এই topic-এর central tweak: **element-এর জন্য নয়, SEGMENT-এর জন্য answer জমাও**। যেকোনো query range `[l, r]`-কে সর্বোচ্চ O(log n)-টা ready segment দিয়ে tile করা যায়, কারণ প্রতি level-এ একটা query সর্বোচ্চ দুটো segment-কে আংশিক কাটে। তাই অল্প কয়েকটা precomputed টুকরো জোড়া দিলেই উত্তর।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **segment tree** — flat array-এ heap layout-এ রাখা: node `i`-র children `2i+1` (বাঁ) আর `2i+2` (ডান), root index 0। Size `4n` সবসময় safe।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
এই exercise-এর পুরো লক্ষ্যই হলো tree-র গঠন হাতে-কলমে অনুভব করা: কীভাবে leaf-গুলো element ধরে, আর internal node-রা নিচ থেকে উপরে combine হয়। একবার এই ছবিটা মাথায় বসে গেলে, build/query/update-এর recursion আর ঝাপসা লাগবে না।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: কোনো tree না বানিয়ে, প্রতিটা query-তে `l` থেকে `r` loop চালিয়ে যোগ করা।
```text
query(1, 4): 5 + 1 + 4 + 9 = 19 (4-টা element ছুঁলাম)
```
এটা একটা query-র জন্য ঠিক আছে, কিন্তু আমাদের লক্ষ্য update-ও সামলানো — সেখানেই tree-র দরকার।
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
প্রতিটা query O(n), আর যদি update-ও থাকে তবে prefix sums-ও O(n)-এ rebuild হয় ([../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/](../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/README.md)-এ দেখা গেছে কেন)। q-টা query + update মিশলে O(n·q) — slow। Tree query আর update দুটোকেই O(log n)-এ নামিয়ে আনে।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **query range সবসময় কয়েকটা ready node-এই ভেঙে যায়**। `query(0,2)` পুরোটাই `[0..2]` node, `query(3,5)` পুরোটাই `[3..5]` node — একটা মাত্র read! `query(1,4)`-ও মাত্র তিনটা ready segment (`[1..1]`, `[2..2]`, `[3..4]`) জোড়া দিয়ে হয়ে যায়।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
Tree-তে নেমে প্রতিটা node-এ তিন-ভাগের সিদ্ধান্ত নাও: node range পুরো query-র ভেতরে হলে তার stored sum নাও আর থামো; পুরো বাইরে হলে 0; আংশিক overlap হলে দুই child-এ নামো। তাই সর্বোচ্চ O(log n)-টা node ছুঁয়েই উত্তর।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "পুরো range যোগ করব" ভাবার বদলে ভাবো "range-টাকে কয়েকটা already-computed segment-এ ভেঙে ফেলব, তারপর ওগুলোর ready উত্তর যোগ করব।" এটাই segment tree-র আত্মা — *store answers for segments, not elements*।
### ছবিতে বোঝা {#7-visual-explanation}
`[2, 5, 1, 4, 9, 3]`-এর উপর tree (প্রতিটা node-এ `[range] = stored sum`):
```text
[0..5] = 24
/ \
[0..2] = 8 [3..5] = 16
/ \ / \
[0..1] = 7 [2..2] = 1 [3..4] = 13 [5..5] = 3
/ \ / \
[0..0]=2 [1..1]=5 [3..3]=4 [4..4]=9
array: index 0 1 2 3 4 5
value 2 5 1 4 9 3
পড়ার নিয়ম: প্রতিটা internal node = বাঁ child + ডান child
root [0..5] পুরো array-র sum ধরে রাখে।
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`query(1, 4)`-এর tree-descent (root থেকে):
1. `[0..5]` — `[1..4]`-এর সাথে আংশিক → দুই child-এ নামো।
2. `[0..2]` — আংশিক → নামো। `[3..5]` — আংশিক → নামো।
3. `[0..1]` — আংশিক → নামো। `[0..0]` বাইরে → 0; `[1..1]` ভেতরে → take 5।
4. `[2..2]` ভেতরে → take 1। `[3..4]` ভেতরে → take 13। `[5..5]` বাইরে → 0।
5. মোট = `5 + 1 + 13 = 19`। ✓ (হাতের উত্তরের সাথে মিলিয়ে নাও)
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
class SegmentTree:
"""RANGE SUM + POINT UPDATE। Element নয়, SEGMENT-এর answer জমায়।
Flat list, heap layout: node i -> children 2i+1 (বাঁ), 2i+2 (ডান)।
Size 4n সবসময় safe। Sum-এর বদলে min/max চাইলে শুধু combine আর
'outside' identity বদলাও (associative হতেই হবে)।"""
def __init__(self, data):
self.n = len(data)
self.tree = [0] * (4 * self.n)
if self.n:
self._build(data, 0, 0, self.n - 1)
def _build(self, data, node, lo, hi):
if lo == hi: # leaf: একটা element
self.tree[node] = data[lo]
return
mid = (lo + hi) // 2
self._build(data, 2 * node + 1, lo, mid) # বাঁ অর্ধেক
self._build(data, 2 * node + 2, mid + 1, hi) # ডান অর্ধেক
self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2]
def query(self, l, r): # inclusive [l, r], 0-indexed
return self._query(0, 0, self.n - 1, l, r)
def _query(self, node, lo, hi, l, r):
if r < lo or hi < l: # পুরো বাইরে
return 0 # sum-এর identity
if l <= lo and hi <= r: # পুরো ভেতরে
return self.tree[node] # ready segment, থামো
mid = (lo + hi) // 2 # আংশিক: ভাঙো
left = self._query(2 * node + 1, lo, mid, l, r)
right = self._query(2 * node + 2, mid + 1, hi, l, r)
return left + right
def brute(data, l, r):
# obviously-correct reference, হাতের উত্তরের সমতুল্য
return sum(data[l:r + 1])
# ---- tests ----
data = [2, 5, 1, 4, 9, 3]
st = SegmentTree(data)
# কাগজে বের করা তিনটা উত্তর মিলিয়ে দেখা
assert st.query(1, 4) == 19 # 5 + 1 + 4 + 9
assert st.query(0, 2) == 8 # 2 + 5 + 1 (একটা ready node)
assert st.query(3, 5) == 16 # 4 + 9 + 3 (একটা ready node)
assert st.query(0, 5) == 24 # root, পুরো array
# সব সম্ভাব্য range exhaustively brute force-এর সাথে মেলানো
for l in range(len(data)):
for r in range(l, len(data)):
assert st.query(l, r) == brute(data, l, r)
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `self.tree = [0] * (4 * self.n)` — recursion-safe size; node `i`-র children `2i+1`, `2i+2`।
- `_build` leaf-এ element বসায়, ফেরার পথে parent = বাঁ child + ডান child।
- `_query` তিন-ভাগের সিদ্ধান্ত: বাইরে → 0, ভেতরে → ready sum, আংশিক → দুই child যোগ।
- `brute` — হাতে যা বের করেছ তার যান্ত্রিক সমতুল্য, fast version verify করতে।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`SegmentTree([2,5,1,4,9,3])` tree বানায় (section 7-এর ছবিটা)। `query(0,2)` সরাসরি `[0..2]=8` node থেকে আসে, `query(3,5)` সরাসরি `[3..5]=16`, আর `query(1,4)` তিন টুকরো জুড়ে `19`। সব assert pass, double loop সব range যাচাই করে। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**Build O(n)** (প্রতিটা node একবার), **প্রতি query O(log n)** (প্রতি level-এ ≤ ~2 node টেকে)।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(n)** — size 4n-এর flat tree array।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- Child index ভুল করা (`2i+1`/`2i+2`-এর বদলে `2i`/`2i+1`) — root index 0-এ পরেরটা চলে না।
- "আংশিক overlap"-এ থেমে stored sum নিয়ে নেওয়া — তাহলে query-র বাইরের element-ও যোগ হয়ে ভুল।
- `[l..r]` inclusive না `[l..r)` half-open — এই note জুড়ে inclusive convention, off-by-one-এ সাবধান।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: recursion + divide and conquer (range অর্ধেক করা, child-দের combine)। গভীর treatment [../segment-tree.md](../segment-tree.md) section 3–5, আর runnable code [../implementation.py](../implementation.py)-তে।
### পরের অনুশীলন {#22-similar-harder-problems}
- Range Sum Query — Mutable (এই tree-তে point update যোগ করা) —