Segment tree — রেঞ্জের প্রশ্ন দ্রুত

১ · সমস্যা — দোকানের হিসাব, প্রশ্ন আর সংশোধন একসাথে

ঢাকার একটি সুপারশপ চেইনের আটটি শাখা — মিরপুর থেকে শুরু করে যাত্রাবাড়ী পর্যন্ত, ক্রমানুসারে ০ থেকে ৭ নম্বর। প্রতিটি শাখার আজকের বিক্রি (লাখ টাকায়) একটি অ্যারেতে: a = [5, 8, 6, 3, 2, 7, 2, 6]. হেড অফিসের ম্যানেজার সারাদিন দুই ধরনের কাজ করেন। প্রশ্ন: “১ থেকে ৬ নম্বর শাখার মোট বিক্রি কত?” আর সংশোধন: “৫ নম্বর শাখার হিসাবে ভুল ছিল, ৭ নয়, আসলে ১০”. এক দিনে হাজার হাজার প্রশ্ন আর সংশোধন মিশে আসে, আর শাখা যদি আটটির বদলে দশ লাখটি হিসাবের ঘর হয় (প্রতি মিনিটের বিক্রি, প্রতিটি পণ্যের মজুদ), তখন প্রতিটি কাজ দ্রুত হওয়া চাই।

এই ধরনের প্রশ্নের নাম range query: অ্যারের একটি অবিচ্ছিন্ন অংশ a[l..r] নিয়ে প্রশ্ন — যোগফল, সর্বনিম্ন (min), সর্বোচ্চ (max). আর একটি ঘরের মান বদলানো হলো point update. দুটি সরল সমাধান আমরা জানি, আর দুটিরই একটি করে দুর্বলতা:

Prefix sum (পর্ব ১৭) প্রশ্নে অসাধারণ: P[r + 1] − P[l], এক বিয়োগ। কিন্তু a[5] বদলালে P[6], P[7], P[8] — পরের সব prefix বদলে যায়, worst case-এ O(n). উল্টো দিকে সরাসরি লুপে বদল O(1), কিন্তু প্রশ্নে O(n). দুই ক্ষেত্রেই n = q = 10⁵ হলে প্রায় 10¹⁰ ধাপ — কয়েক মিনিটের কাজ, যেখানে সময়সীমা এক সেকেন্ড। তার ওপর min আর max-এ prefix কৌশল কাজই করে না, কারণ min-এর কোনো “উল্টো” নেই: [0..7]-এর min আর [0..2]-এর min জেনে [3..7]-এর min বের করা যায় না।

লক্ষ্য তাই একটি মাঝামাঝি ভারসাম্য: প্রশ্ন আর বদল দুটোই O(log n). এমন একটি ভারসাম্যের সরল রূপ হলো অ্যারেকে √n আকারের খণ্ডে ভাগ করা (sqrt decomposition, পর্ব ৩৭) — বদল O(1), প্রশ্ন O(√n). খণ্ডের ভেতরে আবার খণ্ড, তার ভেতরে আবার — এভাবে ভাগ করতে থাকলে আমরা পাই একটি tree, আর √n নেমে আসে log n-এ।

২ · অংশের tree — প্রতিটি node একটি রেঞ্জের হিসাব রাখে

Segment tree একটি binary tree (পর্ব ২৬), যার প্রতিটি node অ্যারের একটি অবিচ্ছিন্ন অংশের (segment) দায়িত্বে। নিয়ম তিনটি:

• Root-এর দায়িত্ব পুরো অ্যারে, [0, n − 1].
• যে node-এর দায়িত্ব [tl, tr] আর tl < tr, তার মাঝখান tm = ⌊(tl + tr)/2⌋; বাঁ সন্তান [tl, tm], ডান সন্তান [tm + 1, tr]. এই অর্থে এটি divide and conquer-এর ভাগাভাগি, যা merge sort-এও দেখেছেন (পর্ব ২১)।
• tl = tr হলে node-টি একটি leaf — ঠিক একটি ঘর a[tl]. আর প্রতিটি internal node-এর মান = দুই সন্তানের মানের যোগ।

আমাদের আট শাখার অ্যারে দিয়ে নিচ থেকে ওপরে tree-টি বানিয়ে দেখুন। প্রতিটি node-এর ওপরের লাইনে তার রেঞ্জ ([2-3] মানে index 2 থেকে 3), নিচের লাইনে সেই রেঞ্জের যোগফল:

এই tree-র তিনটি বৈশিষ্ট্য পুরো পর্বের ভিত্তি। (১) উচ্চতা ছোট: প্রতি স্তরে রেঞ্জের দৈর্ঘ্য প্রায় অর্ধেক হয়, তাই ⌈log₂ n⌉ স্তর পরে দৈর্ঘ্য ১ — উচ্চতা ⌈log₂ n⌉; n = 10⁶-এ মাত্র ২০. (২) node 2n − 1 টি: প্রতিটি internal node-এর ঠিক দুই সন্তান আর leaf n টি, তাই internal node n − 1 টি (প্রতিটি internal node দুটি অংশকে এক করে, n টি অংশ থেকে ১টিতে আসতে n − 1 বার জোড়া)। (৩) একই স্তরের node-গুলোর রেঞ্জ পরস্পর-বিচ্ছিন্ন, আর মিলে সেই স্তরের পুরো অংশ ঢেকে দেয় — query-র প্রমাণে এটিই কাজে লাগবে।

n যদি 2-এর ঘাত না হয়? নিয়ম একই থাকে, শুধু tree আর নিখুঁত (perfect) থাকে না। যেমন n = 6-এ root [0-5], সন্তান [0-2] আর [3-5]; [0-2]-এর সন্তান [0-1] আর [2-2] — একটি leaf এক স্তর আগেই থেমে যায়। উচ্চতা তবু ⌈log₂ 6⌉ = 3, আর node তবু 2·6 − 1 = 11.

৩ · অ্যারেতে tree — index 2v আর 2v + 1, আর 4n কেন যথেষ্ট

Pointer দিয়ে node বানানো যায়, কিন্তু segment tree-র আকার কখনো বদলায় না, তাই একটি সরল অ্যারেই যথেষ্ট — heap-এর মতো (পর্ব ২৩)। 1-based নিয়ম: root-এর index 1; node v-এর বাঁ সন্তান 2v, ডান সন্তান 2v + 1, parent ⌊v/2⌋. আগের ডায়াগ্রামের tree তাই অ্যারেতে এভাবে বসে:

অনেকে 0-based নিয়ম পছন্দ করেন: root 0, সন্তান 2v + 1 আর 2v + 2, parent ⌊(v − 1)/2⌋. দুটিই ঠিক; শুধু একটি কোডে দুটি মেশাবেন না। 1-based-এ গুণ ২ মানে এক bit বাঁয়ে সরানো (v << 1, v << 1 | 1), আর parent মানে v >> 1 — এজন্য কনটেস্টে 1-based বেশি চলে। এই পর্বের সব কোড 1-based tree আর 0-based অ্যারে index ব্যবহার করে।

কত ঘর লাগবে — 4n-এর প্রমাণ

Node 2n − 1 টি, কিন্তু 2v/2v + 1 নিয়মে index-গুলো ফাঁকা ফাঁকা পড়ে যখন n 2-এর ঘাত নয়। n = 6-এ ব্যবহৃত index 1–9, 12, 13 — সবচেয়ে বড় 13, অথচ 2n = 12. তাই 2n ঘর সবসময় যথেষ্ট নয়। দাবি: 4n ঘর (index 0 থেকে 4n − 1) সবসময় যথেষ্ট। যুক্তি: উচ্চতা h = ⌈log₂ n⌉, আর গভীরতা d-এর node-এর index 2^d থেকে 2^d+1 − 1-এর মধ্যে, তাই সবচেয়ে বড় index ≤ 2^h+1 − 1. যেহেতু h < log₂ n + 1, তাই 2^h < 2n, আর 2^h+1 − 1 < 4n − 1. ∎ সীমাটি প্রায় আঁটসাঁট: n = 10-এ সবচেয়ে বড় index 25 (2.5n), আর n = 4160-এ 16257 — প্রায় 3.9n. তাই vector t(4 * n) লেখা নিয়ম; জায়গা Θ(n), কিন্তু ধ্রুবক ৪.

Pseudocode — build (1-based tree, 0-based array)

build(v, tl, tr):
    if tl == tr:  t[v] = a[tl];  return          // leaf
    tm = (tl + tr) / 2                            // integer division
    build(2v, tl, tm);  build(2v+1, tm+1, tr)     // children first
    t[v] = t[2v] + t[2v+1]                        // then combine

call: build(1, 0, n-1)

Build-এর সময়: প্রতিটি node-এ একবার ঢোকা আর একটি যোগ — মোট Θ(2n − 1) = Θ(n). Recurrence-এ লিখলে T(n) = 2T(n/2) + O(1), যার সমাধান master theorem-এ (পর্ব ০৯) Θ(n). Recursion ডায়াগ্রামের মতো স্তর ধরে হিসাব করে না, বরং postorder-এ (আগে বাঁ subtree পুরো, তারপর ডান, তারপর নিজে) — কিন্তু “সন্তান আগে, parent পরে” নিয়মটি দুই ক্রমেই মানা হয়, তাই ফল একই। Recursion-এর গভীরতা উচ্চতার সমান, ⌈log₂ n⌉ + 1 — ১০ লাখ উপাদানেও প্রায় ২১টি stack frame, কোনো ভাষাতেই চিন্তার বিষয় নয়।

৪ · Point update — শুধু leaf থেকে root পর্যন্ত একটি পথ

৫ নম্বর শাখার হিসাব ৭ থেকে ১০ হলো। কোন কোন node-এর মান বদলাবে? ঠিক সেগুলো, যাদের রেঞ্জে index 5 আছে: [5], [4-5], [4-7], [0-7]. প্রতি স্তরে ঠিক একটি — কারণ একই স্তরের রেঞ্জগুলো পরস্পর-বিচ্ছিন্ন। এরা মিলে leaf থেকে root পর্যন্ত একটি পথ। Recursive update root থেকে নামে (pos ≤ tm হলে বাঁয়ে, নইলে ডানে), leaf-এ মান বসায়, আর ফেরার পথে প্রতিটি node নতুন করে দুই সন্তানের যোগ হিসাব করে:

একটি সূক্ষ্ম বিষয়: update-এ আমরা নতুন মান বসিয়েছি (assign). “a[5]-এ ৩ যোগ করুন” ধরনের বদলও একই পথে হয়, শুধু leaf-এ t[v] += 3. আর যোগের ক্ষেত্রে ফেরার পথে আবার হিসাব না করে পথের প্রতিটি node-এ সরাসরি ৩ যোগ করলেও চলে — কিন্তু min বা max-এ সেটি চলে না (min-এর কোনো ঘর বাড়লে min কত হবে, শুধু পুরোনো min দেখে বলা যায় না)। তাই নিরাপদ নিয়ম: leaf বদলান, তারপর ওপরের প্রতিটি node দুই সন্তান থেকে আবার হিসাব করুন।

৫ · Range query — ভেতরে, বাইরে আর আংশিক

এবার মূল প্রশ্ন: “১ থেকে ৬ নম্বর শাখার মোট বিক্রি?” (হালনাগাদ অ্যারে [5, 8, 6, 3, 2, 10, 2, 6]-এ উত্তর 8 + 6 + 3 + 2 + 10 + 2 = 31). Recursive query root থেকে শুরু করে প্রতিটি node-এ দেখে, তার রেঞ্জ [tl, tr] প্রশ্নের রেঞ্জ [l, r]-এর সাথে কীভাবে মেলে। তিনটিই সম্ভাবনা:

• পুরো বাইরে (r < tl বা tr < l): এই node-এর কিছুই লাগবে না — 0 ফেরত দিন (যোগের identity).
• পুরো ভেতরে (l ≤ tl আর tr ≤ r): node-এর জমানো মানটিই পুরোটা কাজে লাগে — t[v] ফেরত দিন, নিচে নামার দরকার নেই।
• আংশিক (বাকি সব): দুই সন্তানকে একই প্রশ্ন করুন, উত্তর দুটি যোগ করুন।

প্রমাণ — প্রতি স্তরে সর্বোচ্চ ৪টি node

দাবি: query(l, r) tree-র প্রতিটি স্তরে সর্বোচ্চ ৪টি node দেখে, আর তাদের মধ্যে সর্বোচ্চ ২টি আংশিক। তাই মোট দেখা node ≤ 4(⌈log₂ n⌉ + 1), সময় O(log n).

যুক্তি: একটি node আংশিক মানে তার রেঞ্জ [tl, tr]-এ প্রশ্নের ভেতরের ঘরও আছে, বাইরের ঘরও। রেঞ্জটি অবিচ্ছিন্ন, তাই তাকে প্রশ্নের একটি “সীমানা” পার হতেই হবে: হয় সে l − 1 আর l দুটোই ধরে (বাঁ সীমানা), নয়তো r আর r + 1 দুটোই ধরে (ডান সীমানা)। একই স্তরের রেঞ্জগুলো পরস্পর-বিচ্ছিন্ন, তাই প্রতিটি সীমানা ঘর-জোড়া ঐ স্তরের সর্বোচ্চ একটি node-এ পড়ে — আসলে l − 1 আর l একই node-এ থাকলে সেই node-ই একমাত্র যে বাঁ সীমানা ধরে। সুতরাং প্রতি স্তরে আংশিক node ≤ ২. শুধু আংশিক node-ই সন্তানে নামে, তাই পরের স্তরে দেখা node ≤ 2 × 2 = ৪. (Root একা, স্তর ০-এ ১টি।) ∎

ডায়াগ্রামে ঠিক তাই: স্তর ২-এ দেখা ৪টি ([0-1], [2-3], [4-5], [6-7]), আংশিক ২টি ([0-1] বাঁ সীমানা 0|1 ধরে, [6-7] ডান সীমানা 6|7 ধরে). একই যুক্তি থেকে আরেকটি ফল: রেঞ্জটি সর্বোচ্চ প্রায় 2⌈log₂ n⌉ টি পুরো-ভেতরের node-এ ভাঙে — একে বলা হয় রেঞ্জের canonical decomposition. Lazy propagation, descent আর আরও অনেক কৌশল এই ভাঙনের ওপর দাঁড়িয়ে।

পুরো কোড — আট শাখা, একটি সংশোধন, আর brute force দিয়ে যাচাই

নিচের প্রোগ্রাম build, update আর query তিনটিই লেখে, tree অ্যারেটি ছাপে (ডায়াগ্রামের সাথে মেলানোর জন্য), তারপর সংশোধনের পর সব ৩৬টি রেঞ্জের উত্তর একটি সরল লুপের (brute force) সাথে মেলায়। নিজের লেখা প্রতিটি segment tree এভাবে যাচাই করার অভ্যাস করুন।

#include <iostream>
#include <vector>
using namespace std;
vector<long long> a, t;                            // t[1] = root, children 2v and 2v+1
void build(int v, int tl, int tr) {
    if (tl == tr) { t[v] = a[tl]; return; }
    int tm = (tl + tr) / 2;
    build(2 * v, tl, tm); build(2 * v + 1, tm + 1, tr);
    t[v] = t[2 * v] + t[2 * v + 1];
}
void update(int v, int tl, int tr, int pos, long long val) {
    if (tl == tr) { t[v] = val; return; }
    int tm = (tl + tr) / 2;
    if (pos <= tm) update(2 * v, tl, tm, pos, val); else update(2 * v + 1, tm + 1, tr, pos, val);
    t[v] = t[2 * v] + t[2 * v + 1];                // recompute on the way back up
}
long long query(int v, int tl, int tr, int l, int r) {
    if (r < tl || tr < l) return 0;                // outside
    if (l <= tl && tr <= r) return t[v];           // fully inside
    int tm = (tl + tr) / 2;                        // partial: ask both children
    return query(2 * v, tl, tm, l, r) + query(2 * v + 1, tm + 1, tr, l, r);
}
int main() {
    a = {5, 8, 6, 3, 2, 7, 2, 6};                  // daily sales of 8 shops
    int n = a.size();
    t.assign(4 * n, 0);
    build(1, 0, n - 1);
    cout << "tree:"; for (int v = 1; v < 2 * n; ++v) cout << ' ' << t[v]; cout << '\n';
    a[5] = 10; update(1, 0, n - 1, 5, 10);
    cout << "after a[5] = 10, root = " << t[1] << " | sum[1..6] = " << query(1, 0, n - 1, 1, 6) << '\n';
    int bad = 0;
    for (int l = 0; l < n; ++l)
        for (int r = l; r < n; ++r) {
            long long s = 0;
            for (int i = l; i <= r; ++i) s += a[i];   // brute force
            bad += query(1, 0, n - 1, l, r) != s;
        }
    cout << "checked " << n * (n + 1) / 2 << " ranges, mismatches = " << bad << '\n';
}

tree: 39 22 17 13 9 9 8 5 8 6 3 2 7 2 6
after a[5] = 10, root = 42 | sum[1..6] = 31
checked 36 ranges, mismatches = 0

def build(v, tl, tr):
    if tl == tr:
        t[v] = a[tl]
        return
    tm = (tl + tr) // 2
    build(2 * v, tl, tm)
    build(2 * v + 1, tm + 1, tr)
    t[v] = t[2 * v] + t[2 * v + 1]

def update(v, tl, tr, pos, val):
    if tl == tr:
        t[v] = val
        return
    tm = (tl + tr) // 2
    if pos <= tm:
        update(2 * v, tl, tm, pos, val)
    else:
        update(2 * v + 1, tm + 1, tr, pos, val)
    t[v] = t[2 * v] + t[2 * v + 1]

def query(v, tl, tr, l, r):
    if r < tl or tr < l:                 # outside
        return 0
    if l <= tl and tr <= r:              # fully inside
        return t[v]
    tm = (tl + tr) // 2                  # partial: ask both children
    return query(2 * v, tl, tm, l, r) + query(2 * v + 1, tm + 1, tr, l, r)

a = [5, 8, 6, 3, 2, 7, 2, 6]             # daily sales of 8 shops
n = len(a)
t = [0] * (4 * n)                        # t[1] = root, children 2v and 2v+1
build(1, 0, n - 1)
print("tree:", *t[1:2 * n])
a[5] = 10
update(1, 0, n - 1, 5, 10)
print("after a[5] = 10, root =", t[1], "| sum[1..6] =", query(1, 0, n - 1, 1, 6))
bad = sum(query(1, 0, n - 1, l, r) != sum(a[l:r + 1]) for l in range(n) for r in range(l, n))
print("checked", n * (n + 1) // 2, "ranges, mismatches =", bad)

tree: 39 22 17 13 9 9 8 5 8 6 3 2 7 2 6
after a[5] = 10, root = 42 | sum[1..6] = 31
checked 36 ranges, mismatches = 0

৬ · শুধু যোগ নয় — যেকোনো সহযোজী কাজ

কোডে যোগ এসেছে মাত্র দুই জায়গায়: parent-এর হিসাব t[2v] + t[2v+1], আর বাইরের node-এর ফেরত মান 0. এই দুটি বদলালেই নতুন প্রশ্নের tree. কিন্তু কোন কাজ বসানো যাবে? শর্ত দুটি:

• সহযোজিতা (associative): (x ∘ y) ∘ z = x ∘ (y ∘ z). Tree রেঞ্জটিকে যেভাবেই টুকরো করুক ([1] ∘ [2-3] ∘ [4-5] ∘ [6], বা অন্য কোনোভাবে), উত্তর একই আসতে হবে।
• Identity element e, যাতে e ∘ x = x — “বাইরে” node-এর ফেরত মান। এই দুই শর্ত মানা গঠনকে বীজগণিতে monoid বলে। (Identity না থাকলেও চলে, বাইরের দিকে না নামলেই হলো — কিন্তু থাকলে কোড সরল।)

লক্ষ করুন, এখানে বিনিময়যোগ্যতা (commutative, x ∘ y = y ∘ x) লাগেনি। Recursive segment tree সবসময় বাঁ সন্তানকে বাঁয়ে আর ডানকে ডানে রেখে জোড়ে, তাই ক্রম ঠিক থাকে। ফলে matrix-এর গুণফল, string hash, বা “একের পর এক প্রয়োগ করা ফাংশন” — যেখানে ক্রম বদলালে উত্তর বদলায় — সেগুলোও segment tree-তে রাখা যায়।

একটি struct জুড়ে নতুন প্রশ্ন — রেঞ্জের মধ্যে সর্বোচ্চ subarray যোগফল

কঠিনতর প্রশ্ন: “শাখা l থেকে r-এর মধ্যে কোন পরপর শাখাগুলোর মোট লাভ সবচেয়ে বেশি?” (লাভ ঋণাত্মকও হতে পারে।) পুরো অ্যারের জন্য এটি maximum subarray সমস্যা, Kadane-এ O(n). কিন্তু প্রতিটি রেঞ্জে নতুন করে Kadane চালালে আবার O(n) প্রতি প্রশ্ন। সমাধান: প্রতিটি node-এ একটি সংখ্যার বদলে চারটি রাখুন —

struct Node { long long sum, pref, suf, best; };   // best = max subarray sum inside
Node leaf(long long x) { return {x, x, x, x}; }
Node combine(const Node& L, const Node& R) {
    return { L.sum + R.sum,
             max(L.pref, L.sum + R.pref),            // best prefix: stays left, or takes all of L
             max(R.suf, R.sum + L.suf),              // best suffix: stays right, or takes all of R
             max({L.best, R.best, L.suf + R.pref}) }; // inside L, inside R, or across the middle
}

যুক্তি: দুই অংশ জোড়া লাগালে সেরা subarray হয় পুরোপুরি বাঁয়ে, পুরোপুরি ডানে, নয়তো মাঝখান পার হয় — আর মাঝ-পার-হওয়াটি হলো বাঁ অংশের সেরা suffix + ডান অংশের সেরা prefix. এই combine সহযোজী (চারটি মানই একটি অবিচ্ছিন্ন অংশের নিখুঁত বর্ণনা, তাই কোন ক্রমে টুকরো জোড়া হলো তাতে কিছু আসে যায় না), কিন্তু বিনিময়যোগ্য নয় — L আর R অদলবদল করলে prefix আর suffix গুলিয়ে যায়। Query-তে শুধু যোগের জায়গায় combine, আর “বাইরে” node বাদ দিন (এখানে identity হিসেবে sum = 0 আর বাকি তিনটি −∞ নেওয়া যায়)। প্রতিটি প্রশ্ন O(log n) — এক struct-এর ধারণা থেকেই। এটি augmented data structure-এর একটি সুন্দর উদাহরণ।

৭ · Iterative segment tree — 2n ঘরে, recursion ছাড়া

Recursive tree পড়তে সহজ, কিন্তু প্রতিটি প্রশ্নে কয়েক ডজন ফাংশন-ডাক আর 4n ঘর। কনটেস্টে আর বাস্তব কোডে জনপ্রিয় একটি বিকল্প আছে, যা নিচ থেকে ওপরে কাজ করে — iterative (bottom-up) segment tree. নিয়ম: অ্যারের আকার ঠিক 2n; leaf a[i] বসে t[n + i]-এ; তারপর v = n − 1 থেকে 1 পর্যন্ত t[v] = t[2v] ∘ t[2v+1]. n যদি 2-এর ঘাত হয় (আমাদের n = 8), এই tree অংশ ৩-এর tree-র সাথে হুবহু এক — leaf t[8..15], root t[1].

• Update(p, x): p += n; t[p] = x; তারপর p > 1 যতক্ষণ, t[p/2] = t[p] ∘ t[p^1], p /= 2. এখানে p ^ 1 হলো p-এর ভাই (শেষ bit উল্টে দিলে 2v ↔ 2v + 1).
• Query [l, r) — half-open, r বাদ: l += n, r += n; যতক্ষণ l < r: l বিজোড় হলে t[l] নিন আর l++; r বিজোড় হলে r−− আর t[r] নিন; তারপর দুটিকেই ২ দিয়ে ভাগ (এক স্তর ওপরে)।

কেন কাজ করে: যদি l একটি ডান সন্তান হয় (বিজোড়), তার parent-এর রেঞ্জে l-এর বাঁয়ের ঘরও আছে, যা প্রশ্নের বাইরে — তাই l-কে আলাদা করে নিয়ে এক ঘর ডানে সরতে হয়। বাঁ সন্তান হলে parent পুরোটা ভেতরে, তাই ওপরে উঠলেই চলে। r-এর দিকে ঠিক উল্টো। হালনাগাদ অ্যারেতে sum[1, 7) (অর্থাৎ index 1..6) হাতে চালান:

একই চারটি node — [1], [6], [2-3], [4-5] — শুধু ভিন্ন ক্রমে, আর কোনো recursion বা আংশিক node-এর ঝামেলা ছাড়া। প্রতি স্তরে সর্বোচ্চ দুটি node নেওয়া হয়, তাই O(log n). নিচের প্রোগ্রাম এই রূপে range minimum রাখে, ইচ্ছে করে n = 10 নিয়ে (2-এর ঘাত নয়), আর সব ৫৫টি রেঞ্জ brute force-এর সাথে মেলায়:

#include <algorithm>
#include <climits>
#include <initializer_list>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
struct MinTree {                                   // iterative, bottom-up: leaves at n..2n-1
    int n; vector<int> t;
    MinTree(const vector<int>& a) : n(a.size()), t(2 * a.size()) {
        for (int i = 0; i < n; ++i) t[n + i] = a[i];
        for (int v = n - 1; v >= 1; --v) t[v] = min(t[2 * v], t[2 * v + 1]);
    }
    void set(int p, int val) {
        p += n; t[p] = val;
        for (; p > 1; p /= 2) t[p / 2] = min(t[p], t[p ^ 1]);   // p ^ 1 = sibling
    }
    int query(int l, int r) {                      // min of a[l..r-1], half-open
        int res = INT_MAX;                         // identity for min
        for (l += n, r += n; l < r; l /= 2, r /= 2) {
            if (l & 1) res = min(res, t[l++]);
            if (r & 1) res = min(res, t[--r]);
        }
        return res;
    }
};
int main() {
    vector<int> a = {5, 8, 6, 3, 2, 7, 2, 6, 9, 4};  // n = 10, not a power of two
    MinTree st(a);
    cout << "min[0,5) = " << st.query(0, 5) << ", min[5,10) = " << st.query(5, 10) << '\n';
    for (auto [p, v] : {pair{4, 11}, pair{6, 1}}) { a[p] = v; st.set(p, v); }
    cout << "after updates: min[0,5) = " << st.query(0, 5) << ", min[5,10) = " << st.query(5, 10) << '\n';
    int bad = 0, cnt = 0;
    for (int l = 0; l < st.n; ++l)
        for (int r = l + 1; r <= st.n; ++r, ++cnt)
            bad += st.query(l, r) != *min_element(a.begin() + l, a.begin() + r);
    cout << "checked " << cnt << " ranges, mismatches = " << bad << '\n';
}

min[0,5) = 2, min[5,10) = 2
after updates: min[0,5) = 3, min[5,10) = 1
checked 55 ranges, mismatches = 0

import math

class MinTree:                           # iterative, bottom-up: leaves at n..2n-1
    def __init__(self, a):
        self.n = n = len(a)
        self.t = [0] * n + list(a)
        for v in range(n - 1, 0, -1):
            self.t[v] = min(self.t[2 * v], self.t[2 * v + 1])

    def set(self, p, val):
        p += self.n
        self.t[p] = val
        while p > 1:
            self.t[p // 2] = min(self.t[p], self.t[p ^ 1])
            p //= 2

    def query(self, l, r):               # min of a[l..r-1], half-open
        res = math.inf
        l, r = l + self.n, r + self.n
        while l < r:
            if l & 1:
                res = min(res, self.t[l]); l += 1
            if r & 1:
                r -= 1; res = min(res, self.t[r])
            l //= 2; r //= 2
        return res

a = [5, 8, 6, 3, 2, 7, 2, 6, 9, 4]       # n = 10, not a power of two
st = MinTree(a)
print(f"min[0,5) = {st.query(0, 5)}, min[5,10) = {st.query(5, 10)}")
for p, v in [(4, 11), (6, 1)]:
    a[p] = v
    st.set(p, v)
print(f"after updates: min[0,5) = {st.query(0, 5)}, min[5,10) = {st.query(5, 10)}")
pairs = [(l, r) for l in range(st.n) for r in range(l + 1, st.n + 1)]
bad = sum(st.query(l, r) != min(a[l:r]) for l, r in pairs)
print("checked", len(pairs), "ranges, mismatches =", bad)

min[0,5) = 2, min[5,10) = 2
after updates: min[0,5) = 3, min[5,10) = 1
checked 55 ranges, mismatches = 0

একটি সতর্কতা: এই query-তে বাঁ দিক থেকে আর ডান দিক থেকে নেওয়া node একই res-এ মেশে, ফলে ক্রম ঠিক থাকে না। min, যোগ, gcd-এর মতো বিনিময়যোগ্য কাজে সমস্যা নেই। কিন্তু অংশ ৬-এর max-subarray struct-এর মতো ক্রম-নির্ভর কাজে দুটি আলাদা accumulator রাখুন — resL = resL ∘ t[l++] আর resR = t[--r] ∘ resR — আর শেষে resL ∘ resR.

৮ · Tree-র ওপর নামা — prefix ≥ k-এর প্রথম index

নতুন প্রশ্ন: “শাখা ০ থেকে শুরু করে ক্রমানুসারে যোগ করলে কোন শাখায় পৌঁছে মোট বিক্রি প্রথমবার ২০ লাখ ছাড়ায় (≥ 20)?” Prefix sum-এর ওপর binary search (পর্ব ১৮) করা যায় — কিন্তু প্রতিটি prefix নিজেই একটি O(log n) query, তাই মোট O(log² n). তার চেয়ে ভালো: tree-র মধ্য দিয়ে সরাসরি নামুন। প্রতিটি node-এ বাঁ সন্তানের যোগফল দেখুন — সেটি ≥ k হলে উত্তর বাঁ দিকেই, নইলে বাঁ দিকের পুরো যোগফল k থেকে বাদ দিয়ে ডানে যান। এই descent এক পথে root থেকে leaf: O(log n).

Pseudocode — first index with prefix sum ≥ k (values ≥ 0; 1-based tree)

firstPrefix(k):
    if t[1] < k:  return -1
    v = 1;  tl = 0;  tr = n-1
    while tl != tr:
        tm = (tl + tr) / 2
        if t[2v] >= k:  v = 2v;  tr = tm                 // answer is on the left
        else:  k = k - t[2v];  v = 2v+1;  tl = tm+1      // skip the whole left part
    return tl

একই ছাঁচে আরও প্রশ্ন: (১) max tree-তে “প্রথম index যেখানে a[i] ≥ x” — বাঁ সন্তানের max ≥ x হলে বাঁয়ে, নইলে ডানে। (২) k-তম ১: 0/1 অ্যারের sum tree-তে k-তম 1-এর অবস্থান — অর্থাৎ “এখনো উপস্থিত উপাদানগুলোর মধ্যে k-তম কে?” কোনো উপাদান মুছতে শুধু তার ঘরে 0 বসান। মানগুলোকে index ধরে (প্রয়োজনে coordinate compression করে) গণনার tree বানালে এটি একটি পরিবর্তনশীল সংগ্রহের order statistic O(log n)-এ দেয়। (৩) একটি রেঞ্জ [l, r]-এর ভেতরে প্রথম শর্তপূরণকারী index — canonical decomposition-এর node-গুলো বাঁ থেকে ডানে দেখুন, প্রথম যে node-এ শর্ত মেলে শুধু তার ভেতরে নামুন; মোট O(log n).

৯ · কোনটি কখন — Fenwick, sparse table, lazy আর মেমরির হিসাব

রেঞ্জের প্রশ্নের জন্য এই মডিউলে আরও কয়েকটি হাতিয়ার আসছে। প্রত্যেকটির নিজস্ব জায়গা আছে:

Fenwick tree বনাম segment tree: শুধু point update আর range sum লাগলে Fenwick ছোট (দশ লাইনের কম), দ্রুত (ধ্রুবক ছোট) আর n + 1 ঘরে চলে। কিন্তু Fenwick prefix-এর উত্তর দেয়; যেকোনো [l, r] পেতে prefix(r) − prefix(l − 1) লাগে, অর্থাৎ বিয়োগ — উল্টো। min-এর উল্টো নেই, তাই সাধারণ range min-এ Fenwick চলে না, segment tree চলে। Sparse table বনাম segment tree: অ্যারে কখনো না বদলালে sparse table min/max-এর প্রতিটি প্রশ্ন O(1)-এ দেয় — দুটি পরস্পর-ঢাকা (overlapping) ঘাত-দৈর্ঘ্যের অংশের min নিয়ে, যা চলে কারণ min(x, x) = x (idempotent). যোগে overlapping চলে না (একই ঘর দুবার গোনা হয়)। আর একটিও update এলে sparse table অচল।

Lazy propagation (পর্ব ৩৫), এক নজরে: “৩ থেকে ৬ নম্বর শাখার সবার বিক্রিতে ২ যোগ করুন” — এই রেঞ্জ আপডেট এখনকার tree-তে প্রতিটি ঘর আলাদা করে বদলায়, O(n log n). Lazy propagation-এর বুদ্ধি: canonical decomposition-এর O(log n) টি node-এ শুধু একটি “বাকি কাজ” চিহ্ন রেখে দিন, আর নিচে তখনই নামান যখন কোনো প্রশ্ন সত্যিই সেখানে যায়। বিস্তারিত পরের পর্বে।

মেমরি আর recursion — বাস্তবের খুঁটিনাটি

• জায়গা: recursive রূপে 4n, iterative-এ 2n. n = 10⁶ আর long long হলে 4n মানে ৩২ MB — অনেক judge-এর ২৫৬ MB সীমায় চলে, কিন্তু একাধিক tree বা struct-node হলে হিসাব করে নিন। মান int-এ ধরলে int রাখুন।
• Recursion: গভীরতা মাত্র ⌈log₂ n⌉ + 1, তাই stack overflow-এর ভয় নেই (DSU-এর লম্বা শিকল বা DFS-এর মতো নয়)। খরচটি গতির: প্রতিটি query কয়েক ডজন ফাংশন-ডাক। C++-এ এটি সাধারণত যথেষ্ট দ্রুত; Python-এ বড় ইনপুটে iterative রূপ নিন।
• Off-by-one: এক কোডে inclusive [l, r] আর অন্য কোডে half-open [l, r) মেশানো segment tree-র সবচেয়ে প্রচলিত বাগ। একটি নিয়ম বেছে ফাংশনের পাশে মন্তব্যে লিখে রাখুন।
• খুব বড় index (যেমন 10⁹ পর্যন্ত অবস্থান, কিন্তু মাত্র 10⁵ টি ব্যবহৃত): 4·10⁹ ঘর অসম্ভব। হয় coordinate compression, নয়তো dynamic segment tree — node শুধু দরকার হলে তৈরি হয়, প্রতি update-এ O(log U) টি নতুন node.

১০ · AI-এর যুগে segment tree — সুন্দর কোড, লুকানো off-by-one

“Segment tree লিখে দাও” — AI প্রায় নিশ্চিতভাবে চলনসই ৩০ লাইন দেবে। কিন্তু segment tree-র বাগ প্রায় কখনো compile error দেয় না, আর ছোট উদাহরণে প্রায়ই উত্তর ঠিক আসে: n = 8-এ 2n ঘর যথেষ্ট, n = 6-এ নয়; সব মান ধনাত্মক হলে min-এর identity 0 ভুল হলেও ধরা পড়ে না, ঋণাত্মক এলে পড়ে। তাই AI-এর কোড নিজের brute force দিয়ে যাচাই না করে জমা দেবেন না।

Segment tree-এর কোডে AI সাধারণত যেসব ভুল করে

Segment tree-এর কোড যাচাইয়ের চেকলিস্ট

• অ্যারের আকার: recursive হলে 4n, iterative হলে 2n; n = 1, 2-এর ঘাত আর 2-এর ঘাত + 1 — তিন ধরনের n-এ চালিয়েছি
• identity ঠিক: যোগে 0, min-এ +∞, max-এ −∞, gcd-এ 0, গুণে 1
• রেঞ্জের নিয়ম (inclusive না half-open) এক জায়গায় লেখা, আর সব ডাক সেই নিয়ম মানে
• Edge case: এক-ঘরের রেঞ্জ, পুরো অ্যারে, প্রথম আর শেষ ঘরে update, ঋণাত্মক মান
• এলোমেলো অ্যারে, update আর query মিশিয়ে হাজারবার brute force-এর সাথে মিলিয়েছি — stress testing
• AI-এর complexity দাবি (build, update, query, জায়গা) আলাদা করে যাচাই করেছি, আর যোগফলের জন্য long long নিয়েছি