003 — Hand-build a Segment Tree¶

অধ্যায় · সমস্ত অনুশীলন ও উৎস · ধাপে ধাপে শেখা

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

প্রশ্ন ও উদাহরণ¶

সহজ করে প্রশ্ন¶

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

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

চেনা উদাহরণে বোঝা¶

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

ভিত্তির ধারণা¶

আগের কোন ধারণাটি লাগবে¶

এটা recursion আর divide and conquer-এর উপর দাঁড়িয়ে। Segment tree বানানো মানে একটা range-কে বারবার অর্ধেক করা — ঠিক merge sort যেভাবে array অর্ধেক করে। প্রতিটা node তার দুই অর্ধেকের উত্তর combine করে নিজের উত্তর বানায়।

ভেতরের যুক্তি¶

লুকানো logic হলো এই topic-এর central tweak: element-এর জন্য নয়, SEGMENT-এর জন্য answer জমাও। যেকোনো query range [l, r]-কে সর্বোচ্চ O(log n)-টা ready segment দিয়ে tile করা যায়, কারণ প্রতি level-এ একটা query সর্বোচ্চ দুটো segment-কে আংশিক কাটে। তাই অল্প কয়েকটা precomputed টুকরো জোড়া দিলেই উত্তর।

কী দিয়ে তথ্য রাখব¶

একটা segment tree — flat array-এ heap layout-এ রাখা: node i-র children 2i+1 (বাঁ) আর 2i+2 (ডান), root index 0। Size 4n সবসময় safe।

এটি কেন উপযুক্ত¶

এই exercise-এর পুরো লক্ষ্যই হলো tree-র গঠন হাতে-কলমে অনুভব করা: কীভাবে leaf-গুলো element ধরে, আর internal node-রা নিচ থেকে উপরে combine হয়। একবার এই ছবিটা মাথায় বসে গেলে, build/query/update-এর recursion আর ঝাপসা লাগবে না।

ধাপে ধাপে সমাধান¶

প্রথম সরল উপায়¶

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

উদাহরণ

query(1, 4): 5 + 1 + 4 + 9 = 19   (4-টা element ছুঁলাম)

এটা একটা query-র জন্য ঠিক আছে, কিন্তু আমাদের লক্ষ্য update-ও সামলানো — সেখানেই tree-র দরকার।

কোথায় বেশি কাজ হচ্ছে¶

প্রতিটা 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)-এ নামিয়ে আনে।

যে বিষয়টি খেয়াল করতে হবে¶

মূল 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]) জোড়া দিয়ে হয়ে যায়।

আরও কম কাজে সমাধান¶

Tree-তে নেমে প্রতিটা node-এ তিন-ভাগের সিদ্ধান্ত নাও: node range পুরো query-র ভেতরে হলে তার stored sum নাও আর থামো; পুরো বাইরে হলে 0; আংশিক overlap হলে দুই child-এ নামো। তাই সর্বোচ্চ O(log n)-টা node ছুঁয়েই উত্তর।

ভাবনার পরিবর্তন¶

মোচড়: "পুরো range যোগ করব" ভাবার বদলে ভাবো "range-টাকে কয়েকটা already-computed segment-এ ভেঙে ফেলব, তারপর ওগুলোর ready উত্তর যোগ করব।" এটাই segment tree-র আত্মা — store answers for segments, not elements।

ছবিতে বোঝা¶

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

ছোট input-এ ধাপে ধাপে¶

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। ✓ (হাতের উত্তরের সাথে মিলিয়ে নাও)

কোড ও ব্যাখ্যা¶

Python¶

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!")

কোডের প্রতিটি অংশ¶

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 মিলিয়ে দেখা¶

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

খরচ ও সাধারণ ভুল¶

সময়¶

Build O(n) (প্রতিটা node একবার), প্রতি query O(log n) (প্রতি level-এ ≤ ~2 node টেকে)।

অতিরিক্ত জায়গা¶

O(n) — size 4n-এর flat tree array।

যে ভুলগুলো এড়াতে হবে¶

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

শেখা ও পরের অনুশীলন¶

ভিত্তির সঙ্গে সম্পর্ক¶

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

পরের অনুশীলন¶

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)

কৌশলটি মনে রাখুন¶

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

নিজেকে যাচাই করুন¶

ভবিষ্যতের আমাকে: 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।