009 — Blank-file Reimplementation¶

Source¶

Original source: self-exercise (এই folder-এর implementation.py-র test-গুলো ব্যবহার করো)
Platform: self-exercise — কোনো judge নেই, ইচ্ছে করেই
Topic: segment tree and fenwick tree
Difficulty: Medium
Pattern: from-memory implementation (দুটো structure-ই blank থেকে আবার লেখা)
Basic idea inherited from: পুরো folder

1. Problem in simple words¶

এটা judge problem নয় — একটা from-memory drill। একটা সম্পূর্ণ খালি file খোলো, কিছু না দেখে দুটো structure-ই আবার লেখো:

1) SegmentTree  — build, point update, range sum (O(log n))
2) Fenwick      — add, prefix_sum, range_sum    (O(log n))

তারপর repo-র assert-গুলো (../implementation.py-র মতো) তাদের উপর চালাও। লক্ষ্য: API মুখস্থ নয়, কেন প্রতিটা লাইন আছে তা বুঝে লেখা।

2. Which basic idea does this inherit from?¶

এটা পুরো folder-এর উপর দাঁড়িয়ে: segment tree-র divide-and-conquer build/query/update, আর Fenwick-এর lowbit navigation। আগের আটটা problem যা শিখিয়েছে, এই exercise সেটা ফাঁকা কাগজে পরীক্ষা করে।

3. What is the hidden math or logic?¶

দুটো structure একই central tweak-এর দুই রূপ: element নয়, segment-এর answer জমাও। Segment tree টা স্পষ্টভাবে tree (heap layout); Fenwick সেই tree-টাকে binary arithmetic-এ লুকিয়ে রাখে — i & (-i) দিয়ে block-গুলোয় hop। Fenwick কম পারে (invertible aggregation মাত্র), কিন্তু code-এর দশ ভাগের এক ভাগে।

4. Which data structure is needed?¶

দুটোই: segment tree (flat list, heap layout, size 4n) আর Fenwick tree (n+1 ঘরের array, 1-indexed)। blank থেকে দুটোই লিখে, একই logical array-র উপর তাদের উত্তর মিলিয়ে দেখো।

5. Why this data structure fits¶

এই drill-এর লক্ষ্য reflex তৈরি: contest-এ যেন দুটোই চোখ বন্ধ করে লিখতে পারো। Segment tree generalize করে (min/max/gcd); Fenwick sum/count-এ সংক্ষিপ্ততম। দুটো পাশাপাশি লিখলে তাদের trade-off (code length, কী পারে, memory) হাড়ে-মজ্জায় বসে যায়।

6. Real-life analogy¶

ভাবো তুমি গাড়ি চালানো শিখছ। প্রথমে instructor-এর পাশে বসে দেখো (আগের problem পড়া), কিন্তু আসল শেখা হয় যখন একা steering ধরো (blank file)। চাকা, gear, brake — প্রতিটা কেন কাজ করছে তা না বুঝে শুধু মুখস্থ করলে নতুন রাস্তায় আটকে যাবে। blank-file reimplementation সেই একা-চালানোর পরীক্ষা।

7. Visual explanation¶

দুটো structure একই array [2, 5, 1, 4, 9, 3] কীভাবে দেখে:

SegmentTree (explicit heap-layout tree):
                  [0..5]=24
                 /         \
         [0..2]=8         [3..5]=16
         /     \           /      \
   [0..1]=7 [2..2]=1  [3..4]=13 [5..5]=3
    /    \              /    \
 [0]=2 [1]=5        [3]=4  [4]=9

Fenwick (same idea, hidden in indices; 1-indexed):
  tree[i] covers the last lowbit(i) elements ending at i
  tree[4] -> a[1..4]   tree[6] -> a[5..6]   tree[2] -> a[1..2]
  prefix_sum(i): hop i -= i & (-i)   |   add(i): hop i += i & (-i)

8. Example input and output¶

array = [2, 5, 1, 4, 9, 3]  (segment tree 0-indexed; Fenwick 1-indexed)

SegmentTree:
  query(1, 4) = 5 + 1 + 4 + 9 = 19
  update(2, 6); query(1, 4)   = 5 + 6 + 4 + 9 = 24

Fenwick:
  range_sum(2, 5) = 5 + 1 + 4 + 9 = 19
  add(3, +5); range_sum(2, 5)   = 5 + 6 + 4 + 9 = 24

দুটোর একই query একই উত্তর দেয় — এটাই self-check।

9. Brute force thinking¶

প্রথম সরল চিন্তা: কোনো structure ছাড়া, প্রতিটা query-তে loop চালিয়ে যোগ আর update-এ সরাসরি array বদলানো। এই brute-টাই reference হিসেবে রেখে দুটো structure verify করব।

brute_range_sum(arr, l, r): return sum(arr[l..r])
update: arr[i] = v

10. Why brute force is slow¶

brute query O(n); update + query মিশলে O(n·q)। কিন্তু এখানে brute-কে আমরা ফেলে দিচ্ছি না — reference oracle হিসেবে ব্যবহার করছি: structure-এর প্রতিটা উত্তর brute-এর সাথে exhaustively মিলিয়ে দেখব। ধীর হলেও brute স্পষ্টভাবে সঠিক, তাই নিখুঁত verifier।

11. Key observation¶

মূল observation: blank-file drill-এর আসল পরীক্ষা হলো invariant মনে রাখা, syntax নয়। Segment tree: parent সবসময় = combine(children)। Fenwick: tree[i] ধরে i-তে শেষ হওয়া lowbit(i)-টা element; query 0-র দিকে hop, update n-এর দিকে। এই invariant ঠিক থাকলে code আপনাআপনি ঠিক হয়।

12. Optimized intuition¶

দুটো structure-ই blank থেকে লেখার পর, একটা mirror array-র সাথে random update + random query চালাও (brute-checked)। দুই structure-ই পাস করলে বুঝবে শুধু মুখস্থ করোনি, invariant-গুলো ঠিকঠাক ধরে রেখেছ। আটকালে আগের নির্দিষ্ট problem/note-এ ফিরে যাও, তারপর আবার blank থেকে চেষ্টা।

13. Thinking tweak¶

মোচড়: "API মুখস্থ করব" থেকে সরে এসে ভাবো "প্রতিটা লাইনের পেছনের invariant বলতে পারব কি না"। যদি বলতে পারো কেন tree[node] = left + right ফেরার পথে দরকার, বা কেন Fenwick 1-indexed — তাহলে code আর মুখস্থ লাগে না, যুক্তি থেকেই বেরিয়ে আসে।

14. Step-by-step dry run¶

blank থেকে লেখার পর self-check (array [2, 5, 1, 4, 9, 3]):

SegmentTree build → root [0..5] = 24।
st.query(1, 4) = 19; Fenwick fw.range_sum(2, 5) = 19 → একমত ✓।
st.update(2, 6) (0-indexed); Fenwick fw.add(3, +5) (1-indexed, delta) — একই element বদলানো।
st.query(1, 4) = 24; fw.range_sum(2, 5) = 24 → আবার একমত ✓।
random op-এ দুটোই brute-এর সাথে মিলে গেলে drill সফল।

15. Python solution¶

class SegmentTree:
    """blank থেকে লেখা: RANGE SUM + POINT UPDATE।
    invariant: parent = combine(left child, right child)।
    heap layout: node i -> 2i+1, 2i+2; size 4n safe।"""

    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:
            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 update(self, i, value):
        self._update(0, 0, self.n - 1, i, value)

    def _update(self, node, lo, hi, i, value):
        if lo == hi:
            self.tree[node] = value
            return
        mid = (lo + hi) // 2
        if i <= mid:
            self._update(2 * node + 1, lo, mid, i, value)
        else:
            self._update(2 * node + 2, mid + 1, hi, i, value)
        self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2]

    def query(self, 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 0
        if l <= lo and hi <= r:
            return self.tree[node]
        mid = (lo + hi) // 2
        return (self._query(2 * node + 1, lo, mid, l, r) +
                self._query(2 * node + 2, mid + 1, hi, l, r))


class Fenwick:
    """blank থেকে লেখা: update-সহ prefix sums, 1-indexed।
    invariant: tree[i] ধরে i-তে শেষ হওয়া lowbit(i)-টা element।
    query 0-র দিকে hop (i -= i&-i); update n-এর দিকে hop (i += i&-i)।"""

    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)

    def add(self, i, delta):
        while i <= self.n:
            self.tree[i] += delta
            i += i & (-i)

    def prefix_sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & (-i)
        return s

    def range_sum(self, l, r):                   # invertible: prefix(r) - prefix(l-1)
        return self.prefix_sum(r) - self.prefix_sum(l - 1)


def brute(arr, l, r):
    # reference oracle: ধীর কিন্তু স্পষ্টভাবে সঠিক
    return sum(arr[l:r + 1])


# ---- tests (repo-style asserts on both structures) ----
data = [2, 5, 1, 4, 9, 3]

# SegmentTree (0-indexed)
st = SegmentTree(data)
assert st.query(1, 4) == 19
st.update(2, 6)
assert st.query(1, 4) == 24

# Fenwick (1-indexed) — একই logical array
fw = Fenwick(len(data))
for i, v in enumerate(data, start=1):
    fw.add(i, v)
assert fw.range_sum(2, 5) == 19              # 0-indexed query(1,4)-এর সমতুল্য
fw.add(3, 6 - 1)                             # element 3 (value 1) -> 6, delta +5
assert fw.range_sum(2, 5) == 24

# দুটো structure random op-এ একই mirror array-র সাথে exhaustively মেলে
import random
random.seed(17)
arr = [random.randint(-9, 9) for _ in range(16)]
st = SegmentTree(arr)
fw = Fenwick(len(arr))
for i, v in enumerate(arr, start=1):
    fw.add(i, v)

for _ in range(600):
    if random.random() < 0.5:                # random point update
        idx = random.randrange(len(arr))
        v = random.randint(-9, 9)
        delta = v - arr[idx]
        arr[idx] = v
        st.update(idx, v)                    # segment tree: set
        fw.add(idx + 1, delta)               # Fenwick: add delta (1-indexed)
    else:                                     # random range query, brute-checked
        l = random.randrange(len(arr))
        r = random.randrange(l, len(arr))
        expected = brute(arr, l, r)
        assert st.query(l, r) == expected
        assert fw.range_sum(l + 1, r + 1) == expected

print("সব test pass!")

16. Line-by-line code explanation¶

SegmentTree — build leaf বসায়, parent = বাঁ + ডান child; update path repair; query তিন-ভাগের decision।
Fenwick — add lowbit যোগ করে covering block-এ, prefix_sum lowbit বিয়োগ করে block জোড়ে, range_sum = prefix difference (invertible বলে)।
brute — reference oracle, দুই structure-কেই verify করে।
random fuzz — segment tree (set) আর Fenwick (delta) একই mirror array-র সাথে 600 op মেলায়; index-offset (0 বনাম 1) সাবধানে সামলানো।

17. Output walkthrough¶

দুটো structure blank থেকে লেখা হলো। SegmentTree query(1,4) 19, update-এর পর 24; Fenwick range_sum(2,5) একই 19 ও 24 — তারা একমত। তারপর 600 random op-এ দুটোই একই mirror array-র brute উত্তরের সাথে মেলে (set বনাম delta, index-offset ঠিকঠাক)। সব assert pass। শেষে print: সব test pass!।

18. Time complexity¶

SegmentTree: build O(n), query/update O(log n)। Fenwick: add/prefix_sum/range_sum O(log n), build O(n log n)। সব operation log n।

19. Space complexity¶

O(n) দুটোতেই — segment tree size 4n, Fenwick n+1।

20. Common mistakes¶

Fenwick-কে "set" semantics দেওয়া (delta-র বদলে value add) — set করতে v - current add করো।
segment tree 0-indexed আর Fenwick 1-indexed গুলিয়ে ফেলা — fuzz-এ l+1, r+1 shift মনে রাখো।
API মুখস্থ করে invariant ভুলে যাওয়া — তখন সামান্য variant (min tree, range update) এলেই আটকে যাবে।

21. Which basic problem this inherits from¶

ভিত্তি: পুরো folder — ../segment-tree.md, ../fenwick-tree.md, ../visual-explanation.md, আর reference ../implementation.py (এর test-গুলোই এখানে নিজের code-এ চালাও)।

22. Similar harder problems¶

Dynamic Range Minimum Queries (min tree — combine বদলে blank থেকে লেখো) — CSES "Dynamic Range Minimum Queries" (এই tracker-এর #7)
Count Inversions two ways (BIT কে frequency table হিসেবে নতুন করে ভাবা) — self-exercise (#10)
Hotel Queries (max tree বেয়ে নামা — নতুন descent লেখা) — CSES "Hotel Queries" (#15)

23. Pattern learned¶

From-memory implementation: দুটো structure-ই blank থেকে, invariant বুঝে লেখা। এই reflex না থাকলে contest-এ structure ঠিক চিনলেও type করতে গিয়ে আটকাবে। মুখস্থ নয়, যুক্তি থেকে গড়ে তোলা — এটাই আসল mastery-র চিহ্ন।

24. Final summary¶

ভবিষ্যতের আমাকে: segment tree আর Fenwick দুটোই খালি কাগজ থেকে, প্রতিটা লাইনের invariant বলতে বলতে লিখতে পারা চাই। Segment tree generalize করে, Fenwick সংক্ষিপ্ত — দুটোর trade-off হাড়ে বসিয়ে নাও। এই drill নিয়মিত করলে #10 থেকে #18 পর্যন্ত সব problem-এ structure-টা আর বাধা থাকবে না, শুধু idea-টাই চ্যালেঞ্জ হবে।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।