Problem link ও উৎস
- **Original source:** self-exercise — Codeforces problemset থেকে rating-1500+ একটা unsolved data-structures problem নিজে বাছা
- **Platform:** Codeforces —
- **Topic:** segment tree and fenwick tree
- **Difficulty:** Hard
- **Pattern:** pattern recognition in the wild (editorial খোলার আগে structure চিনে নেওয়া)
- **Basic idea inherited from:** পুরো folder
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
এটা কোনো নির্দিষ্ট judge problem নয় — একটা **recognition drill**। তোমার কাজ: Codeforces problemset-এ গিয়ে rating 1500+ একটা data-structures problem বাছো যেটা তুমি আগে solve করোনি, আর **editorial/tag খোলার আগে** নিজে ঠিক করো — "এখানে কি segment tree/Fenwick লাগবে? কেন?"
এই note-টা সেই decision process-কে একটা পুনরাবৃত্তিযোগ্য checklist বানায়, আর একটা representative "disguised" problem-এ সেটা চালিয়ে দেখায়। উদাহরণ-task: একটা array-তে point update + range-max query — কিন্তু statement-এ "segment tree" শব্দটা কোথাও নেই।
```text
array: [1, 3, 2, 7, 9, 11]
ops:
query max over [1, 3] -> ?
update index 4 -> 0
query max over [3, 5] -> ?
```
### সরাসরি একটি প্রশ্ন দিয়ে শুরু {#_1}
[Codeforces 339D · Xenia and Bit Operations](https://codeforces.com/problemset/problem/339/D) দিয়ে শুরু করতে পারেন। প্রতি level-এ OR/XOR বদলায়; point update-এর পরে root-এর মান বের করতে হবে। নিচের drill-এর worked example আলাদা; সেটিকে এই judge problem-এর সম্পূর্ণ সমাধান ভাববেন না।
### Input ও output {#8-example-input-and-output}
```text
array = [1, 3, 2, 7, 9, 11]
query max [1, 3] = max(3, 2, 7) = 7
update index 4 -> 0 (array = [1, 3, 2, 7, 0, 11])
query max [3, 5] = max(7, 0, 11) = 11
signal: "update + range max" -> segment tree, statement-এ নাম না থাকলেও।
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো তুমি একজন অভিজ্ঞ মেকানিক। গাড়ি গ্যারাজে এলে মালিক বলে না "carburetor বদলাও" — বলে "চড়াইয়ে উঠতে গেলে ঝাঁকায়, আর মাইলেজ কমে গেছে"। উপসর্গ শুনেই তুমি যন্ত্রটা ধরে ফেলো।
Contest statement ঠিক তেমন: কেউ লেখে না "segment tree ব্যবহার করো" — লেখে "values বদলায়, আর বারবার একটা range-এর সবচেয়ে বড়টা চাই"। উপসর্গ → যন্ত্র। এই note সেই উপসর্গ-পড়ার অভ্যাসটাই গড়ে।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা দাঁড়িয়ে আছে **পুরো folder**-এর উপর — segment tree ([../segment-tree.md](../segment-tree.md)), Fenwick ([../fenwick-tree.md](../fenwick-tree.md)), আর তাদের সব variant। কিন্তু এখানে নতুন skill কোনো algorithm নয়, বরং **signal recognition**: একটা অপরিচিত statement পড়ে কোন structure-এর দিকে যাচ্ছে সেটা ধরা।
আগের সব problem তোমাকে structure-গুলো দিয়েছে; এই problem দেয় ওগুলো *কখন* লাগবে তা চেনার চোখ — interview আর contest দুটোতেই আসল পার্থক্য এটাই গড়ে দেয়।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic হলো একটা **trigger-word → structure mapping**। বেশিরভাগ statement structure-এর নাম বলে না; বলে এমন একটা combination যা শুধু এক ধরনের structure-ই efficiently সামলায়:
```text
"আপডেট হতে থাকা array" + "range sum/count" -> Fenwick
"আপডেট" + "range min/max/gcd" -> segment tree
"একটা পুরো range-এ যোগ/বদল করো" -> lazy propagation
"প্রথম index যেখানে value >= target" (with updates) -> segment tree descent
"কতগুলো value ছোট/বড়" (offline, বড় value) -> BIT over compressed values
```
এই mapping মুখস্থ হলে statement পড়েই structure বেরিয়ে আসে।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
নির্ভর করে কোন signal ধরা পড়ল তার উপর — পুরো folder-এর decision tree ([README.md](README.md)-এর "decision drill"):
```text
no updates? -> prefix sums (tree বানিও না)
updates + sums/counts? -> Fenwick
updates + min/max/gcd,
range updates,
বা tree-descent trick? -> segment tree
```
উদাহরণ-task (update + range max) → **segment tree** (Fenwick arbitrary range-এ max পারে না)।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
এই drill-এর পুরো লক্ষ্য: structure-কে statement-এর ভাষায় না খুঁজে, *operation-জোড়া*-র ভাষায় খোঁজা। "update + range max" দেখা মাত্রই Fenwick বাদ পড়ে ([../fenwick-tree.md](../fenwick-tree.md) section 8), আর segment tree-র associative-combine generalization ([../segment-tree.md](../segment-tree.md) section 8, `combine = max`) ঠিক বসে যায়।
এই reasoning-ই efficient — কারণ ভুল structure বাছলে হয় TLE (brute), নয় wrong answer (Fenwick দিয়ে max)। সঠিক recognition প্রথমেই সময় বাঁচায়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা (recognition-এর আগে যেটা সবাই ভাবে): কোনো structure ছাড়াই — প্রতিটা query-তে `l..r` loop চালিয়ে max বের করো, প্রতিটা update array-তে সরাসরি বসাও।
```text
query(l, r): best = max(array[l..r]) # O(n) প্রতিবার
update(i, v): array[i] = v # O(1)
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
প্রতিটা range-max query O(n)। `q`-টা query থাকলে **O(n·q)** — Codeforces-এর typical `n, q ~ 2·10^5`-এ প্রায় 4·10^10 operation, নিশ্চিত TLE। এই TLE-র সম্ভাবনাই হলো **signal**: "updates + repeated range aggregate, বড় n" দেখা মাত্রই brute বাদ, log-time structure চাই।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **structure-এর নাম statement-এ থাকে না; থাকে operation-জোড়া**। "একটা array যা update হয় + বারবার একটা range-এর aggregate" — এই জোড়াটাই segment tree/Fenwick-এর সর্বজনীন fingerprint। aggregate-টা invertible (sum/count) হলে Fenwick; min/max/gcd বা range-update হলে segment tree।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
Signal ধরা পড়লে বাকিটা যান্ত্রিক: উদাহরণ-task-এ "update + range max" → max segment tree বানাও (`combine = max`, identity `-inf`), `query(l, r)` তিন-ভাগের decision-এ ([../segment-tree.md](../segment-tree.md) section 5), `update(i, v)` root-to-leaf path repair (section 6)। সব operation O(log n)।
আসল drill: Codeforces problem-এ এই recognition প্রয়োগ করো, editorial শুধু confirm করতে খোলো — আগে নয়।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "এই problem-টা কী চাইছে" না ভেবে ভাবো "এই problem কোন *operation জোড়া* চাইছে — update + কী aggregate?" structure তখন statement থেকে নয়, জোড়া থেকে বেরিয়ে আসে। Recognition হয়ে যায় reflex, lookup নয়।
### ছবিতে বোঝা {#7-visual-explanation}
একটা disguised statement থেকে signal বের করার flow:
```text
statement পড়ো
|
v
"array বদলায়?" --no--> prefix sums / static trick (tree নয়)
| yes
v
"কী aggregate?" --sum/count--> Fenwick (সবচেয়ে ছোট code)
|
| min / max / gcd বা range-update বা "first value >= target"
v
segment tree
|
v
"একটা পুরো range-এ update?" --yes--> + lazy propagation
উদাহরণ: "values বদলায়" + "range max" -> segment tree (max combine)
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Recognition + solve, উদাহরণ-task-এ:
1. Statement: "values বদলায়, বারবার range-এর max"। Signal: update + range max।
2. Mapping: max invertible নয় → Fenwick বাদ → **segment tree** (max combine)।
3. `query max [1, 3]` on `[1,3,2,7,...]` → `max(3,2,7) = 7`।
4. `update index 4 -> 0` → array `[1,3,2,7,0,11]`, tree-র এক path repair।
5. `query max [3, 5]` → `max(7,0,11) = 11`। ✓
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
class MaxSegmentTree:
"""RANGE MAX + POINT UPDATE — 'update + range max' signal-এর canonical যন্ত্র।
combine = max, 'outside' identity = -inf (max-এর neutral element)।
Flat list, heap layout: node i -> children 2i+1, 2i+2। Size 4n safe।
Statement-এ 'segment tree' নাম না থাকলেও এই operation-জোড়াই একে ডেকে আনে।"""
NEG_INF = float('-inf')
def __init__(self, data):
self.n = len(data)
self.tree = [self.NEG_INF] * (4 * self.n)
if self.n:
self._build(data, 0, 0, self.n - 1)
def _build(self, data, node, lo, hi):
if lo == hi:
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] = max(self.tree[2 * node + 1], self.tree[2 * node + 2])
def update(self, i, v): # array[i] = v
self._update(0, 0, self.n - 1, i, v)
def _update(self, node, lo, hi, i, v):
if lo == hi:
self.tree[node] = v
return
mid = (lo + hi) // 2
if i <= mid:
self._update(2 * node + 1, lo, mid, i, v)
else:
self._update(2 * node + 2, mid + 1, hi, i, v)
self.tree[node] = max(self.tree[2 * node + 1], self.tree[2 * node + 2])
def query(self, l, r): # max over inclusive [l, r]
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 self.NEG_INF # max-এর identity
if l <= lo and hi <= r: # পুরো ভেতরে
return self.tree[node]
mid = (lo + hi) // 2 # আংশিক: ভাঙো
return max(self._query(2 * node + 1, lo, mid, l, r),
self._query(2 * node + 2, mid + 1, hi, l, r))
def classify(updates_present, aggregate):
"""recognition drill-টাই code-এ: signal -> structure-এর নাম।
এটা solver নয়, 'কোন যন্ত্র' সিদ্ধান্ত-টা আনুষ্ঠানিক করা।"""
if not updates_present:
return "prefix sums" # frozen array, tree নয়
if aggregate in ("sum", "count"):
return "fenwick" # invertible, ছোট code
if aggregate in ("min", "max", "gcd"):
return "segment tree" # invertible নয়, tree চাই
return "segment tree" # range-update ইত্যাদি
def brute_max(data, l, r):
# obviously-correct reference
return max(data[l:r + 1])
# ---- tests ----
# 1) recognition drill সঠিক mapping দেয়
assert classify(False, "sum") == "prefix sums" # update নেই -> tree নয়
assert classify(True, "sum") == "fenwick" # update + sum
assert classify(True, "count") == "fenwick"
assert classify(True, "max") == "segment tree" # Fenwick max পারে না
assert classify(True, "min") == "segment tree"
assert classify(True, "gcd") == "segment tree"
# 2) ধরা-পড়া structure (segment tree, max) সত্যিই কাজ করে
data = [1, 3, 2, 7, 9, 11]
st = MaxSegmentTree(data)
assert st.query(1, 3) == 7 # max(3, 2, 7)
st.update(4, 0) # data -> [1,3,2,7,0,11]
data[4] = 0
assert st.query(3, 5) == 11 # max(7, 0, 11)
assert st.query(0, 5) == 11
# 3) random fuzz: tree max vs brute, update মিশিয়ে
import random
random.seed(18)
for _ in range(300):
n = random.randint(1, 12)
arr = [random.randint(-20, 20) for _ in range(n)]
seg = MaxSegmentTree(arr)
for _ in range(20):
if random.random() < 0.4: # update
i = random.randrange(n)
v = random.randint(-20, 20)
seg.update(i, v)
arr[i] = v
else: # query
l = random.randrange(n)
r = random.randint(l, n - 1)
assert seg.query(l, r) == brute_max(arr, l, r)
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `MaxSegmentTree` — `combine = max`, identity `-inf`; `_build`/`_update`/`_query` ঠিক sum-tree-র গঠন, শুধু combine আর identity বদলানো ([../segment-tree.md](../segment-tree.md) section 8)।
- `_query` তিন-ভাগের decision: বাইরে → `-inf`, ভেতরে → stored max, আংশিক → দুই child-এর max।
- `classify` — recognition drill-টাকে code-এ রূপ দেওয়া: signal (update আছে কি, কোন aggregate) → structure-এর নাম।
- `brute_max` — fast tree-র উত্তর যাচাই করার obviously-correct reference।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
প্রথমে `classify` যাচাই করে signal→structure mapping সঠিক (update নেই → prefix sums; update+sum → Fenwick; update+max/min/gcd → segment tree)। তারপর ধরা-পড়া max segment tree আসল task চালায়: `query(1,3)=7`, update-এর পর `query(3,5)=11`। শেষে 300 random fuzz (update মিশিয়ে) brute-এর সাথে মেলে। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
উদাহরণ-task: build **O(n)**, প্রতিটা query/update **O(log n)** — `q` op মিলিয়ে **O(n + q log n)**। (Recognition নিজে O(1) চিন্তা, কিন্তু সেটাই brute-এর O(n·q) trap এড়ায়।)
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(n)** — size 4n-এর flat tree array।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- Statement-এ structure-এর নাম খোঁজা — নাম কখনো লেখা থাকে না; operation-জোড়া দেখো।
- Update থাকা সত্ত্বেও prefix sums-এ থাকা — প্রতিটা update O(n) rebuild, TLE ([../segment-tree.md](../segment-tree.md) section 1)।
- Range max-এ Fenwick ধরা — arbitrary range-এ max invertible নয়, ভুল answer ([../fenwick-tree.md](../fenwick-tree.md) section 8)।
- Editorial আগে খোলা — তাহলে recognition skill-টাই train হয় না; নিজে signal বের করার পর শুধু confirm করতে খোলো।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: পুরো folder — segment tree ([../segment-tree.md](../segment-tree.md)), Fenwick ([../fenwick-tree.md](../fenwick-tree.md)), তাদের সব variant, আর [README.md](README.md)-এর decision drill। এই problem সেগুলোকে নতুন কিছু শেখায় না; শেখায় কখন কোনটা ডেকে আনতে হবে।
### পরের অনুশীলন {#22-similar-harder-problems}
- যেকোনো Codeforces "Educational Round" Div-2 D/E data-structures problem — recognition drill-এর আসল মাঠ —