Lazy propagation — রেঞ্জ আপডেট

১ · সমস্যা — পুরো একটি রেঞ্জ বদলাতে গেলে segment tree হাঁপিয়ে ওঠে

একটি ব্যাংকের কথা ভাবুন। গ্রাহকদের অ্যাকাউন্ট নম্বর ০ থেকে n − 1, আর প্রতিটি অ্যাকাউন্টে কিছু টাকা আছে। দুই ধরনের কাজ বারবার আসে। প্রথমটি একসাথে জমা: “একটি গার্মেন্টস কারখানার ঈদ বোনাস — অ্যাকাউন্ট ২০০ থেকে ৪৫০ পর্যন্ত সবার অ্যাকাউন্টে ৫০০ টাকা”. দ্বিতীয়টি হিসাবের প্রশ্ন: “অ্যাকাউন্ট ৩০০ থেকে ৯০০ পর্যন্ত মোট কত টাকা আছে?” — হয়তো একটি শাখার মোট আমানত জানতে। দুটি কাজ মিশে আসে, লাখ লাখ বার।

দ্বিতীয় কাজটি একটি range query, আর প্রথমটি একটি range update. পর্ব ৩৪-এ আপনি segment tree দেখেছেন: অ্যারের ওপর একটি binary tree, যার প্রতিটি node একটি রেঞ্জের যোগফল রাখে, আর রেঞ্জের যোগফল আর point update দুটোই O(log n). এই পর্বে আমরা ধরে নিচ্ছি সেই কাঠামো আপনার চেনা — build, query আর point update কীভাবে হয়, তা আবার বলছি না। প্রশ্ন একটাই: পুরো রেঞ্জ একসাথে বদলাতে চাইলে কী হয়?

সরল উপায়গুলো কোথায় আটকায়

উপায় ১ — প্রতিটি ঘরে আলাদা point update. [l, r]-এর k = r − l + 1 টি ঘরের প্রতিটিতে O(log n), মোট O(k log n). পুরো অ্যারেতে বোনাস দিলে O(n log n) — একটি মাত্র কাজে! দশ লাখ অ্যাকাউন্ট আর এক লাখ এমন কাজে প্রায় ২ × 10¹² ধাপ।

উপায় ২ — tree-টি ওপর থেকে নেমে রেঞ্জের সব leaf বদলানো, ফেরার পথে যোগফল ঠিক করা. এতে প্রতিটি node একবার করে ছোঁয়া হয়, কিন্তু [l, r]-এর ভেতরের প্রতিটি leaf আর তাদের সব পূর্বপুরুষ — কমপক্ষে k টি node, পুরো অ্যারেতে প্রায় 2n. এটি Θ(k + log n), worst case Θ(n). একটি সাধারণ অ্যারেতে লুপ চালানোর চেয়ে ভালো কিছু নয়।

উপায় ৩ — prefix sum বা difference array (পর্ব ১৭). Prefix sum-এ প্রশ্ন O(1), কিন্তু একটি আপডেটের পর পুরো prefix অ্যারে নতুন করে বানাতে হয় — O(n). Difference array-তে রেঞ্জ আপডেট O(1), কিন্তু যোগফল জানতে আগে পুরোটা জমাতে হয় — O(n). যতক্ষণ প্রশ্ন আর আপডেট মিশে আসে (online), এদের কেউ একা যথেষ্ট নয়।

শেষ সারির কৌশলটির নাম lazy propagation — “অলস প্রচার”. এর পুরো রহস্য একটি বাক্যে: যে কাজ এখনই কারও দরকার নেই, তা এখনই করবেন না.

২ · অলস হওয়ার বুদ্ধি — অফিসের ড্রয়ারে একটি নোট

Segment tree-তে ঠিক এটিই। প্রতিটি node v দুটি জিনিস রাখে:

• sum[v] — v-এর রেঞ্জের যোগফল, v-এর নিজের নোটসহ ঠিক।
• tag[v] — একটি lazy tag: “v-এর রেঞ্জের প্রতিটি ঘরে এখনো tag[v] যোগ করা বাকি, কিন্তু শুধু v-এর সন্তানদের কাছে” — v নিজে ইতিমধ্যে হিসাব করে ফেলেছে।

দুটি ছোট কাজ সবকিছু চালায়। apply(v, x): node v-এর পুরো রেঞ্জে x যোগ করা — অর্থাৎ sum[v] += x × (রেঞ্জের দৈর্ঘ্য) আর tag[v] += x. এটি O(1), সন্তানদের না ছুঁয়ে। আর push-down push(v): v-এর নোট দুই সন্তানের হাতে দেওয়া — দুই সন্তানে apply(child, tag[v]), তারপর tag[v] = 0. সন্তানদের মান ঠিক হয়ে গেল, আর তারাও এখন নিজেদের নোট রাখে। নিচ থেকে ওপরের দিকে উল্টো কাজটির নাম pull-up: sum[v] = sum[left] + sum[right].

Pseudocode — range add on [ql, qr] (0-based, node v covers [l, r])

update(v, l, r, ql, qr, x):
    if qr < l or r < ql:  return              // disjoint: nothing to do
    if ql <= l and r <= qr:                    // fully covered:
        apply(v, l, r, x);  return              //   fix sum[v], write the note, STOP
    m = (l + r) / 2
    push(v, l, m, r)                            // partial: hand old note down first
    update(2v, l, m, ql, qr, x)
    update(2v+1, m+1, r, ql, qr, x)
    sum[v] = sum[2v] + sum[2v+1]                // pull up

এই পর্বে node-এর নম্বর পর্ব ৩৪-এর প্রচলিত নিয়মে: root = 1, node v-এর বাঁ সন্তান 2v, ডান সন্তান 2v + 1, অ্যারে 4n আকারের। মূল কথা দ্বিতীয় শর্তে — পুরোপুরি ঢাকা node-এ পৌঁছালেই থামুন, নিচে নামবেন না। এবার একটি সত্যিকারের অ্যারেতে দেখুন: a = [5, 3, 7, 2, 6, 1, 4, 8], আর কাজ “[2, 5]-এর প্রতিটি ঘরে 10 যোগ”.

৩ · Push-down — নোট নিচে নামে ঠিক যখন দরকার

বাসি leaf-গুলো কি কখনো সমস্যা করবে? করবে — যদি কেউ নোট না নামিয়েই তাদের পড়ে। নিয়মটি তাই সরল আর কঠোর: কোনো node-এর সন্তানের কাছে যাওয়ার আগে, সবসময় সেই node-এর নোট push করুন — update-এ আর query-তে, দুই জায়গাতেই। Query-র কোড পর্ব ৩৪-এর মতোই, শুধু একটি লাইন বেশি:

Pseudocode — range sum on [ql, qr] (0-based)

query(v, l, r, ql, qr):
    if qr < l or r < ql:  return 0
    if ql <= l and r <= qr:  return sum[v]    // already correct, tag included
    m = (l + r) / 2
    push(v, l, m, r)                            // the one new line
    return query(2v, l, m, ql, qr) + query(2v+1, m+1, r, ql, qr)

আগের আপডেটের পর এবার জিজ্ঞেস করুন: [3, 4]-এর যোগফল কত? সঠিক উত্তর a[3] + a[4] = (2 + 10) + (6 + 10) = 28. দেখুন নোটগুলো কীভাবে ঠিক যেখানে দরকার, সেখানে নামে:

ভুল কোথায় হতে পারে, এখান থেকেই বোঝা যায়। Query-তে push বাদ দিলে ধাপ ৪-এ [3] থেকে বাসি মান 2 ফেরত আসত, আর উত্তর হতো 2 + 6 = 8. আবার update-এ নামার আগে push বাদ দিলে আরেক রকম ভুল: পুরোনো নোট থেকে যাবে ওপরে, আর pull-up সন্তানদের বাসি মান যোগ করে ওপরের ঠিক মানটিকে নষ্ট করবে। তাই নিয়ম: নামার আগে push, ফেরার পরে pull.

৪ · কোড — range add আর range sum, brute force-এর সাথে মিলিয়ে

এবার পুরো কোড। ব্যাংকের গল্পের ছোট রূপ: আটটি অ্যাকাউন্ট, একটি নির্দিষ্ট ক্রমের কাজ — '+' মানে রেঞ্জে জমা (ঋণাত্মক হলে উত্তোলন), '?' মানে রেঞ্জের মোট। প্রতিটি প্রশ্নের উত্তর একটি সাধারণ অ্যারের brute force লুপের সাথে মেলানো হচ্ছে — নতুন ডেটা স্ট্রাকচার লিখলে এটিই প্রথম পরীক্ষা। টাকার যোগফল বড় হতে পারে, তাই long long; x × দৈর্ঘ্য গুণটিতে integer overflow সবচেয়ে সহজে ঢোকে।

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
vector<ll> a = {5, 3, 7, 2, 6, 1, 4, 8};
int n = a.size();
vector<ll> s(4 * n), tag(4 * n);            // s = segment sum, tag = pending add
void build(int v, int l, int r) {
    if (l == r) { s[v] = a[l]; return; }
    int m = (l + r) / 2;
    build(2 * v, l, m); build(2 * v + 1, m + 1, r); s[v] = s[2 * v] + s[2 * v + 1];
}
void apply(int v, int l, int r, ll x) { s[v] += x * (r - l + 1); tag[v] += x; }
void push(int v, int l, int m, int r) {     // hand the note down to both children
    if (tag[v]) { apply(2 * v, l, m, tag[v]); apply(2 * v + 1, m + 1, r, tag[v]); tag[v] = 0; }
}
void update(int v, int l, int r, int ql, int qr, ll x) {
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) { apply(v, l, r, x); return; }   // fully covered: write the note, stop
    int m = (l + r) / 2; push(v, l, m, r);
    update(2 * v, l, m, ql, qr, x); update(2 * v + 1, m + 1, r, ql, qr, x);
    s[v] = s[2 * v] + s[2 * v + 1];                          // pull up
}
ll query(int v, int l, int r, int ql, int qr) {
    if (qr < l || r < ql) return 0;
    if (ql <= l && r <= qr) return s[v];
    int m = (l + r) / 2; push(v, l, m, r);
    return query(2 * v, l, m, ql, qr) + query(2 * v + 1, m + 1, r, ql, qr);
}
int main() {
    build(1, 0, n - 1);
    struct Op { char t; int l, r; ll x; };
    vector<Op> ops = {{'+', 2, 5, 10}, {'?', 0, 7, 0}, {'?', 3, 4, 0}, {'+', 0, 3, -2},
                      {'?', 1, 2, 0}, {'+', 4, 7, 5}, {'?', 2, 6, 0}, {'?', 5, 5, 0}};
    for (auto [t, l, r, x] : ops) {
        ll got = 0, want = 0;
        if (t == '+') update(1, 0, n - 1, l, r, x); else got = query(1, 0, n - 1, l, r);
        for (int i = l; i <= r; ++i) { if (t == '+') a[i] += x; else want += a[i]; }   // brute force copy
        if (t == '+') cout << "add " << x << " to [" << l << ',' << r << "]\n";
        else cout << "sum[" << l << ',' << r << "] = " << got << "  brute = " << want
                  << "  " << (got == want ? "ok" : "MISMATCH") << '\n';
    }
}

add 10 to [2,5]
sum[0,7] = 76  brute = 76  ok
sum[3,4] = 28  brute = 28  ok
add -2 to [0,3]
sum[1,2] = 16  brute = 16  ok
add 5 to [4,7]
sum[2,6] = 71  brute = 71  ok
sum[5,5] = 16  brute = 16  ok

a = [5, 3, 7, 2, 6, 1, 4, 8]
n = len(a)
s, tag = [0] * (4 * n), [0] * (4 * n)       # s = segment sum, tag = pending add
def build(v, l, r):
    if l == r:
        s[v] = a[l]; return
    m = (l + r) // 2
    build(2 * v, l, m); build(2 * v + 1, m + 1, r)
    s[v] = s[2 * v] + s[2 * v + 1]
def apply(v, l, r, x):                      # add x to every cell of node v
    s[v] += x * (r - l + 1); tag[v] += x
def push(v, l, m, r):                       # hand the note down to both children
    if tag[v]:
        apply(2 * v, l, m, tag[v]); apply(2 * v + 1, m + 1, r, tag[v]); tag[v] = 0
def update(v, l, r, ql, qr, x):
    if qr < l or r < ql: return
    if ql <= l and r <= qr:
        apply(v, l, r, x); return           # fully covered: write the note and stop
    m = (l + r) // 2; push(v, l, m, r)
    update(2 * v, l, m, ql, qr, x); update(2 * v + 1, m + 1, r, ql, qr, x)
    s[v] = s[2 * v] + s[2 * v + 1]          # pull up
def query(v, l, r, ql, qr):
    if qr < l or r < ql: return 0
    if ql <= l and r <= qr: return s[v]
    m = (l + r) // 2; push(v, l, m, r)
    return query(2 * v, l, m, ql, qr) + query(2 * v + 1, m + 1, r, ql, qr)
build(1, 0, n - 1)
ops = [("+", 2, 5, 10), ("?", 0, 7), ("?", 3, 4), ("+", 0, 3, -2),
       ("?", 1, 2), ("+", 4, 7, 5), ("?", 2, 6), ("?", 5, 5)]
for t, l, r, *x in ops:
    if t == "+":
        update(1, 0, n - 1, l, r, x[0])
        for i in range(l, r + 1): a[i] += x[0]    # brute force copy
        print(f"add {x[0]} to [{l},{r}]")
    else:
        got, want = query(1, 0, n - 1, l, r), sum(a[l:r + 1])
        print(f"sum[{l},{r}] = {got}  brute = {want}  {'ok' if got == want else 'MISMATCH'}")

add 10 to [2,5]
sum[0,7] = 76  brute = 76  ok
sum[3,4] = 28  brute = 28  ok
add -2 to [0,3]
sum[1,2] = 16  brute = 16  ok
add 5 to [4,7]
sum[2,6] = 71  brute = 71  ok
sum[5,5] = 16  brute = 16  ok

৫ · কেন ঠিক, আর কেন O(log n) — প্রমাণ

সঠিকতা

দাবি: প্রতিটি কাজের পর ওপরের invariant সত্য থাকে, আর query সঠিক উত্তর দেয়। শুরুতে (build-এর পর) কোনো নোট নেই, আর প্রতিটি sum[v] নিজের রেঞ্জের যোগফল — invariant সত্য। এবার দেখুন প্রতিটি মৌলিক কাজ invariant রাখে কি না।

• apply(v, x): v-এর রেঞ্জের প্রতিটি ঘরে সত্যিই x যোগ হয়েছে ধরে নিলে নতুন যোগফল sum[v] + x·len — ঠিক সেটিই লেখা হয়। v-এর সন্তানরা এই x জানে না, কিন্তু সেটি এখন v-এর tag-এ — “পূর্বপুরুষের ঝুলে থাকা নোট”, invariant যা অনুমতি দেয়।
• push(v): v-এর নোট দুই সন্তানে apply হলো আর v থেকে মুছল। সন্তানদের জন্য ঝুলে থাকা নোট থেকে এটি সরে তাদের নিজের মানে ঢুকল — invariant সত্য। নাতিদের জন্য নোটটি এখন সন্তানের গায়ে, তাই তাদের দিক থেকেও কিছু বদলায়নি।
• pull-up: push-এর পর v-এর নিজের tag ০, তাই v-এর রেঞ্জের যোগফল = দুই সন্তানের যোগফলের যোগ — ঠিক।

Query যে node-গুলোর মান ফেরত দেয়, সেগুলোতে পৌঁছানোর পথে সব পূর্বপুরুষ push করেছে — তাই তাদের মান পুরোপুরি সঠিক। আর ফেরত দেওয়া node-গুলোর রেঞ্জ ঠিক [ql, qr]-কে ভাগ করে (পর্ব ৩৪-এর যুক্তি), তাই যোগফল সঠিক। ∎ Induction-টি কাজের সংখ্যার ওপর: প্রতিটি কাজ invariant মেনে শুরু করে, invariant মেনে শেষ করে।

জটিলতা — প্রতিটি level-এ সর্বোচ্চ চারটি node

Update বা query-তে একটি node দেখা হলে তিন অবস্থার একটি: (ক) পুরোপুরি বাইরে, (খ) পুরোপুরি ঢাকা — দুই ক্ষেত্রেই O(1) কাজ করে থামে; (গ) আংশিক — শুধু এই node-ই নিচে নামে। দাবি: কোনো একটি level-এ সর্বোচ্চ দুটি node আংশিক. কারণ একই level-এর node-গুলোর রেঞ্জ পাশাপাশি, একে অন্যকে ছেদ না করে বসানো; একটি node আংশিক হতে হলে তার রেঞ্জের ভেতরে [ql, qr]-এর একটি প্রান্ত (ql বা qr-এর কিনারা) থাকতেই হবে — নইলে সে হয় পুরো ঢাকা, নয় পুরো বাইরে। প্রান্ত মাত্র দুটি, তাই আংশিক node সর্বোচ্চ দুটি। প্রতিটি আংশিক node পরের level-এ দুটি সন্তান দেখে, তাই প্রতিটি level-এ দেখা node সর্বোচ্চ ২ × ২ = ৪. Tree-র উচ্চতা ⌈log₂ n⌉, তাই একটি কাজে মোট দেখা node ≤ 4⌈log₂ n⌉ + 1.

প্রতিটি দেখা node-এ কাজ O(1): একটি push (দুটি apply), দুটি তুলনা, একটি pull-up. তাই প্রতিটি range update আর range query worst case-এ O(log n) — amortized নয়, প্রতিটি কাজেই। এখানে একটি শর্ত লুকিয়ে আছে, পরের অংশে যা বারবার আসবে: apply আর push প্রতিটি O(1) হতে হবে — অর্থাৎ tag থেকে node-এর নতুন মান সন্তানদের না দেখে বের করা যায়, আর দুটি tag জুড়ে একটি tag বানানো যায়। Build O(n), জায়গা sum আর tag মিলে 8n টি ঘর — O(n). ওপরের ডায়াগ্রামে [2, 5]-এর আপডেট ৭টি node দেখেছে, সীমা 4 × 3 + 1 = 13-এর অনেক নিচে।

৬ · Range assign আর tag-এর গঠন — সবচেয়ে প্রচলিত বাগ

যোগ ছাড়াও আরেকটি স্বাভাবিক আপডেট: range assign — “[l, r]-এর প্রতিটি ঘরের মান এখন থেকে c”. ব্যাংকের ভাষায়: একটি প্রকল্প শেষে কিছু অ্যাকাউন্টের ব্যালান্স নির্দিষ্ট একটি অঙ্কে বসিয়ে দেওয়া। একা assign-এর tag সহজ: node-এর নোট “সবাই c”, apply করলে sum[v] = c × len. কিন্তু খেয়াল করুন, এখানে “নোট নেই” আর “c = 0” আলাদা — 0-তে বসানোও একটি বৈধ আপডেট। তাই একটি আলাদা চিহ্ন (bool বা sentinel) লাগে।

আসল পরীক্ষা আসে যখন একই tree-তে add আর assign দুটোই চলে। একটি node-এ ধারাবাহিকভাবে কয়েকটি নোট জমতে পারে, আর তাদের ক্রম গুরুত্বপূর্ণ: “+3, তারপর 5-এ বসাও” মানে শেষে সবাই 5; কিন্তু “5-এ বসাও, তারপর +3” মানে সবাই 8. যেকোনো ক্রমের নোটকে একটি ছোট tag-এ গুটিয়ে রাখতে হয় — এর নাম tag composition. সমাধানটি হলো tag-কে একটি নির্দিষ্ট রূপে রাখা: (set, add) মানে “আগে set থাকলে সবাইকে set-এ বসাও, তারপর add যোগ করো”. এখন যেকোনো নতুন নোট এই রূপে মেশানো যায়:

আর push-এ সন্তানের হাতে নোট দিতে হয় একই ক্রমে: আগে set, তারপর add. উল্টো ক্রমে দিলে — আগে add, তারপর set — সন্তানের set তার সদ্য-পাওয়া add মুছে দেয়। কোডটি compile হবে, অনেক পরীক্ষায় উত্তরও ঠিক আসবে, কারণ ভুলটি শুধু তখনই দেখা দেয় যখন একটি node-এ set আর add দুটোই একসাথে ঝুলে থাকে। একটি node-এ ধাপে ধাপে দেখুন:

এবার দুটি tree পাশাপাশি — একটিতে সঠিক push, অন্যটিতে “আগে add” — আর দুটিকেই brute force-এর সাথে মেলানো। কোড ছোট রাখতে build-এর বদলে প্রতিটি ঘরে আলাদা assign (O(n log n), এখানে সমস্যা নয়)।

#include <iostream>
#include <string>
#include <vector>
using namespace std; using ll = long long;
struct Seg {                              // range assign + range add, range sum
    int n; bool addFirst; vector<ll> s, st, ad; vector<bool> has;   // has[v]: assign pending
    Seg(const vector<ll>& a, bool bug) : n(a.size()), addFirst(bug), s(4 * n), st(4 * n), ad(4 * n), has(4 * n)
        { for (int i = 0; i < n; ++i) update(1, 0, n - 1, i, i, '=', a[i]); }   // build by point assigns
    void apply(int v, int len, char k, ll x) {
        if (k == '=') { s[v] = x * len; st[v] = x; has[v] = true; ad[v] = 0; }   // assign wipes old adds
        else { s[v] += x * len; ad[v] += x; }                                 // add goes after any assign
    }
    void push(int v, int l, int m, int r) {
        for (char k : string(addFirst ? "+=" : "=+")) {                      // correct order: '=' first
            ll x = (k == '=') ? st[v] : ad[v];
            if (k == '=' ? bool(has[v]) : x != 0) { apply(2 * v, m - l + 1, k, x); apply(2 * v + 1, r - m, k, x); }
        }
        has[v] = false; ad[v] = 0;
    }
    void update(int v, int l, int r, int ql, int qr, char k, ll x) {
        if (qr < l || r < ql) return;
        if (ql <= l && r <= qr) { apply(v, r - l + 1, k, x); return; }
        int m = (l + r) / 2; push(v, l, m, r);
        update(2 * v, l, m, ql, qr, k, x); update(2 * v + 1, m + 1, r, ql, qr, k, x);
        s[v] = s[2 * v] + s[2 * v + 1];
    }
    ll query(int v, int l, int r, int ql, int qr) {
        if (qr < l || r < ql) return 0;
        if (ql <= l && r <= qr) return s[v];
        int m = (l + r) / 2; push(v, l, m, r);
        return query(2 * v, l, m, ql, qr) + query(2 * v + 1, m + 1, r, ql, qr);
    }
};
int main() {
    vector<ll> a = {5, 3, 7, 2, 6, 1, 4, 8}; Seg good(a, false), bad(a, true);
    struct Op { char t; int l, r; ll x; };
    vector<Op> ops = {{'=', 0, 7, 5}, {'+', 0, 7, 2}, {'?', 2, 3, 0}, {'=', 2, 5, 1}, {'+', 4, 7, 3}, {'?', 0, 7, 0}, {'?', 4, 5, 0}};
    for (auto [t, l, r, x] : ops) {
        ll brute = 0; for (int i = l; i <= r; ++i) { if (t == '=') a[i] = x; else if (t == '+') a[i] += x; else brute += a[i]; }
        if (t == '?') { cout << "sum[" << l << ',' << r << "]: correct = " << good.query(1, 0, 7, l, r) << ", brute = "
                             << brute << ", add-first bug = " << bad.query(1, 0, 7, l, r) << '\n'; continue; }
        good.update(1, 0, 7, l, r, t, x); bad.update(1, 0, 7, l, r, t, x);
        cout << (t == '=' ? "set " : "add ") << x << " on [" << l << ',' << r << "]\n";
    }
}

set 5 on [0,7]
add 2 on [0,7]
sum[2,3]: correct = 14, brute = 14, add-first bug = 10
set 1 on [2,5]
add 3 on [4,7]
sum[0,7]: correct = 44, brute = 44, add-first bug = 36
sum[4,5]: correct = 8, brute = 8, add-first bug = 8

class Seg:                                  # range assign + range add, range sum
    def __init__(self, a, add_first=False):
        self.n, self.add_first = len(a), add_first
        self.s, self.st, self.ad = [0] * (4 * self.n), [None] * (4 * self.n), [0] * (4 * self.n)
        for i, x in enumerate(a): self.update(1, 0, self.n - 1, i, i, "=", x)
    def apply(self, v, ln, kind, x):
        if kind == "=": self.s[v], self.st[v], self.ad[v] = x * ln, x, 0   # assign wipes old adds
        else: self.s[v] += x * ln; self.ad[v] += x                         # add goes after any assign
    def push(self, v, l, m, r):
        order = ["+", "="] if self.add_first else ["=", "+"]               # correct order: "=" first
        for kind in order:
            x = self.st[v] if kind == "=" else self.ad[v]
            if x is None or (kind == "+" and x == 0): continue
            self.apply(2 * v, m - l + 1, kind, x); self.apply(2 * v + 1, r - m, kind, x)
        self.st[v], self.ad[v] = None, 0
    def update(self, v, l, r, ql, qr, kind, x):
        if qr < l or r < ql: return
        if ql <= l and r <= qr: return self.apply(v, r - l + 1, kind, x)
        m = (l + r) // 2; self.push(v, l, m, r)
        self.update(2 * v, l, m, ql, qr, kind, x); self.update(2 * v + 1, m + 1, r, ql, qr, kind, x)
        self.s[v] = self.s[2 * v] + self.s[2 * v + 1]
    def query(self, v, l, r, ql, qr):
        if qr < l or r < ql: return 0
        if ql <= l and r <= qr: return self.s[v]
        m = (l + r) // 2; self.push(v, l, m, r)
        return self.query(2 * v, l, m, ql, qr) + self.query(2 * v + 1, m + 1, r, ql, qr)

a = [5, 3, 7, 2, 6, 1, 4, 8]
good, bad = Seg(a), Seg(a, add_first=True)
ops = [("=", 0, 7, 5), ("+", 0, 7, 2), ("?", 2, 3), ("=", 2, 5, 1), ("+", 4, 7, 3), ("?", 0, 7), ("?", 4, 5)]
for t, l, r, *x in ops:
    if t == "?":
        g, b = good.query(1, 0, 7, l, r), bad.query(1, 0, 7, l, r)
        print(f"sum[{l},{r}]: correct = {g}, brute = {sum(a[l:r + 1])}, add-first bug = {b}")
        continue
    good.update(1, 0, 7, l, r, t, x[0]); bad.update(1, 0, 7, l, r, t, x[0])
    for i in range(l, r + 1): a[i] = x[0] if t == "=" else a[i] + x[0]
    print(f"{'set' if t == '=' else 'add'} {x[0]} on [{l},{r}]")

set 5 on [0,7]
add 2 on [0,7]
sum[2,3]: correct = 14, brute = 14, add-first bug = 10
set 1 on [2,5]
add 3 on [4,7]
sum[0,7]: correct = 44, brute = 44, add-first bug = 36
sum[4,5]: correct = 8, brute = 8, add-first bug = 8

সাধারণ নিয়মটি এভাবে মনে রাখুন। প্রতিটি tag আসলে একটি ফাংশন f: “প্রতিটি ঘরের মান x-কে f(x) করো”. দুটি নোট পরপর এলে — প্রথমে g, তারপর f — মিলিত নোট f∘g, অর্থাৎ x → f(g(x)). ফাংশন জোড়ার ক্রম সাধারণত বদলানো যায় না (set আর add তার প্রমাণ), তাই নতুন নোট সবসময় পুরোনোটির “পরে” বসে। Push-এ parent-এর নোট সন্তানের পুরোনো নোটের পরে বসে, কারণ parent-এর নোট সময়ের দিক থেকে নতুন — সন্তানের নোট parent-এর নোটের আগে জমা হয়েছিল (নইলে আগেই push হয়ে যেত)।

৭ · Range min/max, XOR flip আর অন্য জুটি — কোন tag কোথায় চলে

Range add-এর সাথে প্রশ্ন যদি যোগফল না হয়ে সর্বনিম্ন (min) বা সর্বোচ্চ (max) হয়? কোড প্রায় একই — শুধু apply বদলায়। রেঞ্জের প্রতিটি ঘরে x যোগ করলে সবচেয়ে ছোট ঘরটিও x বাড়ে, তাই mn[v] += x — দৈর্ঘ্য দিয়ে গুণ নেই. যোগফলের কোড কপি করে min বানাতে গিয়ে × len রেখে দেওয়া একটি পরিচিত ভুল। Range assign-এ mn[v] = c. Pull-up হয় min(mn[2v], mn[2v+1]).

প্রতিটি নতুন সমস্যায় দুটি প্রশ্ন করুন। (১) Tag থেকে node-এর নতুন মান কি শুধু node-এর পুরোনো মান আর দৈর্ঘ্য দিয়েই বের হয়? (২) দুটি tag কি একটি tag-এ গুটানো যায়? দুটির উত্তর হ্যাঁ হলে lazy propagation চলবে, প্রতিটি কাজ O(log n).

শেষ সারিটি শিক্ষণীয়: “প্রতিটি ঘরকে x-এ ছেঁটে দাও” আপডেটের পর নতুন যোগফল নির্ভর করে কোন ঘরগুলো x-এর চেয়ে বড় ছিল তার ওপর — শুধু পুরোনো যোগফল দিয়ে তা জানা যায় না। শর্ত (১) ভাঙল, তাই সাধারণ lazy চলে না (অংশ ৮-এর “আরও গভীরে” দেখুন)। গুণ-যোগের সারিটিও লক্ষ করুন: ×b তারপর +c একটি affine ফাংশন x → bx + c, আর দুটি affine ফাংশন জুড়লে আবার affine — তাই tag দুটি সংখ্যাতেই থাকে।

XOR tag — রাস্তার বাতির সারি

সিটি করপোরেশনের একটি রাস্তায় n টি বাতি, প্রতিটি জ্বলছে (1) বা নিভে আছে (0). নিয়ন্ত্রণকক্ষ থেকে আদেশ আসে “[l, r]-এর প্রতিটি বাতির সুইচ উল্টে দাও” — জ্বলা নেভে, নেভা জ্বলে; আর প্রশ্ন আসে “[l, r]-এ এখন কয়টি জ্বলছে?”. Node রাখে জ্বলা বাতির সংখ্যা cnt; উল্টালে জ্বলা হয় নেভা, তাই নতুন cnt = len − cnt. Tag একটি bit: “নিচে একবার উল্টানো বাকি”. দুবার উল্টালে আগের অবস্থা — তাই tag মেশানো মানে XOR: t ^= 1. চারটি বাতি 1 0 1 1-এ দেখুন:

৮ · প্রয়োগ, আর কখন lazy tree লাগেই না

তিনটি চেনা প্রয়োগ

• দেয়াল রং করা (interval painting). একটি লম্বা দেয়াল n ভাগে; বিভিন্ন দল [l, r] অংশটি রং c-তে রং করে, পরের রং আগেরটি ঢেকে দেয়। প্রশ্ন: “ঘর i-এর রং কী?”, বা “[l, r]-এ কতগুলো ঘর রং c?”. এটি range assign — নতুন নোট পুরোনোটিকে পুরোপুরি মুছে দেয়। একটি node-এ “পুরো রেঞ্জ এক রঙের কি না, হলে কোন রং” রাখলে প্রশ্নের উত্তরও সহজ।
• বাতি বা সুইচ (flip). ওপরের XOR tag. একই ছাঁচে একটি bit-স্ট্রিংয়ের রেঞ্জ উল্টানো আর “কয়টি 1” গোনা — কনটেস্টে খুব পরিচিত।
• ব্যাংকের অ্যাকাউন্ট. একসাথে জমা বা উত্তোলন (range add), সুদ যোগ (range multiply — affine tag), নির্দিষ্ট অঙ্কে বসানো (range assign), আর মোট বা সর্বনিম্ন ব্যালান্সের প্রশ্ন (“কোনো অ্যাকাউন্ট কি ঋণাত্মক হলো?” — এর জন্য range min লাগে)। বাস্তবের ব্যাংক অবশ্যই প্রতিটি লেনদেন আলাদা করে লেখে; কিন্তু হিসাব-বিশ্লেষণ বা সিমুলেশনে এই ধাঁচ কাজে আসে।

বিকল্প — সবসময় সবচেয়ে সরল যন্ত্রটি বেছে নিন

সব আপডেট আগে, সব প্রশ্ন পরে? তাহলে lazy tree অপচয়। পর্ব ১৭-এর difference array-তে প্রতিটি রেঞ্জ আপডেট O(1) (d[l] += x; d[r+1] -= x), শেষে একবার prefix sum নিয়ে অ্যারে বানান, আরেকবার prefix sum নিয়ে প্রতিটি রেঞ্জের যোগফল O(1) — মোট O(n + q). এটি offline পরিস্থিতির সেরা উত্তর।

শুধু range add আর range sum, মিশ্র ক্রমে? দুটি Fenwick tree (BIT) দিয়েই হয়, যা পর্ব ৩৬-এ বিস্তারিত দেখবেন। ধারণাটির একটি ঝলক: 1-based-এ [l, r]-এ x যোগ করতে B1-এ l-এ +x, r + 1-এ −x, আর B2-এ l-এ +x·(l − 1), r + 1-এ −x·r; তখন প্রথম i টি ঘরের যোগফল = B1-এর prefix(i) × i − B2-এর prefix(i). কোড অনেক ছোট আর দ্রুত — কিন্তু শুধু যোগের জন্য। Assign, min বা flip এলে segment tree-তেই ফিরতে হয়।

আরও সরল কিছু চাই? Sqrt decomposition (পর্ব ৩৭) অ্যারেকে √n আকারের ব্লকে ভাগ করে, আর পুরো ব্লকের জন্য একটি “ব্লক-নোট” রাখে — ঠিক lazy tag-এর এক-স্তরের রূপ। প্রতিটি কাজ O(√n), কিন্তু কোড সহজ আর অদ্ভুত ধরনের আপডেটেও চলে।

৯ · AI-এর যুগে lazy segment tree — চল্লিশ লাইনের কোড, এক লাইনের ভুল

“Lazy segment tree লিখে দাও” — AI সহকারী কয়েক সেকেন্ডে সুন্দর কোড দেবে, আর প্রায়ই সেটি নমুনা ইনপুটে ঠিক উত্তরও দেবে। সমস্যা হলো, lazy tree-র প্রায় সব ভুল নীরব: compile হয়, চলে, অনেক ইনপুটে ঠিক উত্তর দেয়, আর হঠাৎ একটি নির্দিষ্ট ক্রমের কাজে ভুল সংখ্যা ফেরত দেয়। অংশ ৬-এর ভুল push ক্রম তিনটির দুটি প্রশ্নে ধরা পড়েছিল, একটিতে পড়েনি। আর complexity জিজ্ঞেস করলে AI কখনো “O(log n) amortized” বলে — অথচ এখানে প্রতিটি কাজ worst case-এই O(log n); amortized শব্দটি segment tree beats-এর জন্য।

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

Lazy tree যাচাইয়ের চেকলিস্ট

• Update আর query দুই জায়গাতেই সন্তানে নামার আগে push, আর update-এ ফেরার পরে pull-up আছে
• apply node-এর মান আর tag দুটোই বদলায়; tag মেশানোর ক্রম “পুরোনো, তারপর নতুন”
• Edge case: n = 1, n ২-এর ঘাত নয়, l = r, পুরো অ্যারে, ঋণাত্মক x, 0-তে assign
• ছোট n-এ হাজার হাজার এলোমেলো কাজ চালিয়ে brute force অ্যারের সাথে মিলিয়েছি — stress testing
• একটি ছোট উদাহরণ খাতায় dry run করেছি — কোন node-এ কখন নোট বসে আর নামে
• AI-এর complexity দাবি যাচাই করেছি: প্রতিটি কাজ worst case O(log n), জায়গা O(n)