003 — Hand-build a Segment Tree¶

Source¶

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

1. Problem in simple words¶

এটা judge problem নয় — একটা hand-tracing exercise। তোমার কাজ: array [2, 5, 1, 4, 9, 3]-এর জন্য একটা sum segment tree কাগজে আঁকো। প্রতিটা node-এ থাকবে একটা segment আর তার sum। তারপর তিনটা query-র উত্তর হাতে বের করো:

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 দিয়ে নিজের হাতের উত্তর মিলিয়ে নাও।

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 আর ঝাপসা লাগবে না।

6. Real-life analogy¶

একটা company-র org chart ভাবো। প্রতিটা কর্মী (leaf) নিজের একটা সংখ্যা ধরে আছে। প্রতিটা manager (internal node) তার সরাসরি অধীনস্থদের মোট রাখে, আর CEO (root) পুরো company-র মোট। কেউ যদি জিজ্ঞেস করে "এই কটা team-এর মোট কত", তুমি কয়েকজন manager-এর কাছ থেকে ready মোট নিয়েই উত্তর দিয়ে দাও — প্রতিটা কর্মীকে আলাদা করে জিজ্ঞেস করতে হয় না।

7. Visual explanation¶

[2, 5, 1, 4, 9, 3]-এর উপর tree (প্রতিটা node-এ [range] = stored sum):

                      [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 ধরে রাখে।

8. Example input and output¶

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-তে!)

9. Brute force thinking¶

প্রথম সরল চিন্তা: কোনো tree না বানিয়ে, প্রতিটা query-তে l থেকে r loop চালিয়ে যোগ করা।

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/-এ দেখা গেছে কেন)। 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।

14. Step-by-step dry run¶

query(1, 4)-এর tree-descent (root থেকে):

[0..5] — [1..4]-এর সাথে আংশিক → দুই child-এ নামো।
[0..2] — আংশিক → নামো। [3..5] — আংশিক → নামো।
[0..1] — আংশিক → নামো। [0..0] বাইরে → 0; [1..1] ভেতরে → take 5।
[2..2] ভেতরে → take 1। [3..4] ভেতরে → take 13। [5..5] বাইরে → 0।
মোট = 5 + 1 + 13 = 19। ✓ (হাতের উত্তরের সাথে মিলিয়ে নাও)

15. Python solution¶

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 করতে।

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!।

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-এ সাবধান।

21. Which basic problem this inherits from¶

ভিত্তি: recursion + divide and conquer (range অর্ধেক করা, child-দের combine)। গভীর treatment ../segment-tree.md section 3–5, আর runnable code ../implementation.py-তে।

22. Similar harder problems¶

Range Sum Query — Mutable (এই tree-তে point update যোগ করা) — https://leetcode.com/problems/range-sum-query-mutable/ (এই tracker-এর #5)
Dynamic Range Minimum Queries (sum-এর বদলে min combine) — CSES "Dynamic Range Minimum Queries" (#7)
Hotel Queries (এই max tree বেয়ে নামা) — CSES "Hotel Queries" (#15)

23. Pattern learned¶

Build + query tracing: segment tree-র গঠন হাতে আঁকতে পারা — leaf element ধরে, internal node combine করে, query কয়েকটা ready segment-এ ভাঙে। এই mental model ছাড়া বাকি সব tree problem ঝাপসা থাকবে।

24. Final summary¶

ভবিষ্যতের আমাকে: segment tree মানেই segment-এর answer জমানো, element-এর নয়। যেকোনো range কয়েকটা ready node-এ ভেঙে যায় — তাই query O(log n)। এই ছবিটা (section 7) চোখ বন্ধ করে আঁকতে পারা চাই; তাহলে #5 থেকে #15 পর্যন্ত প্রতিটা tree problem স্রেফ এই ভিত্তির উপর variation।

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