""" Segment Tree আর Fenwick Tree (Binary Indexed Tree) — reference implementation। এই পুরো folder-এর big idea: শুধু আলাদা আলাদা element-এর জন্য না, array-র SEGMENT-গুলোর জন্য pre-computed answer জমাও। তাহলে যেকোনো range query হয়ে যায় O(log n)-টা ready segment-এর union, আর যেকোনো point update মাত্র O(log n)-টা segment-কে invalid করে। নিচের দুটো class-ই standard-library-only, আর comment ঠাসা। File-টা সরাসরি চালাও: সব assert pass করতেই হবে, আর একটা ছোট demo print হয়। """ class SegmentTree: """RANGE SUM + POINT UPDATE-এর জন্য segment tree। - build: O(n) প্রতিটা node একবার computed হয় - query: O(log n) প্রতি level-এ সর্বোচ্চ ~2-টা node টেকে - update: O(log n) ঠিক একটা root-to-leaf path repair হয় Tree-টা একটা flat list-এ রাখা, heap layout-এ: node i -> children 2*i + 1 (left) আর 2*i + 2 (right) Recursive layout-এর জন্য size 4*n সবসময়ই যথেষ্ট। Sum-এর বদলে min/max/gcd চাইলে শুধু এ দুটো বদলাও: * combine step (`+` -> min / max / gcd), আর * "fully outside" হলে return করা identity (0 -> +inf / -inf / 0)। Combine-টা ASSOCIATIVE হতেই হবে, কারণ tree grouping-টা fix করে দেয়। """ def __init__(self, data): self.n = len(data) self.tree = [0] * (4 * self.n) # recursion-এর জন্য safe size if self.n: self._build(data, 0, 0, self.n - 1) # ---- build: divide and conquer ------------------------------------ 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) # ডান অর্ধেক # parent-এর answer = দুই অর্ধেকের combination self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2] # ---- point update: data[i] = value সেট করো ------------------------- def update(self, i, value): """Element i-কে `value` বানাও (0-indexed)।""" self._update(0, 0, self.n - 1, i, value) def _update(self, node, lo, hi, i, value): if lo == hi: # target leaf-এ পৌঁছে গেছি self.tree[node] = value return mid = (lo + hi) // 2 if i <= mid: # leaf-টা বাঁ অর্ধেকে থাকে self._update(2 * node + 1, lo, mid, i, value) else: # ... নাহলে ডান অর্ধেকে self._update(2 * node + 2, mid + 1, hi, i, value) # recursion থেকে ফেরার পথে এই node-টা repair করো self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2] # ---- range query: data[l..r] inclusive-এর sum ---------------------- def query(self, l, r): """Inclusive range [l, r]-এর element-গুলোর sum return করো (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: # query-র পুরোপুরি OUTSIDE return 0 # sum-এর identity if l <= lo and hi <= r: # query-র পুরোপুরি INSIDE return self.tree[node] # ready-made answer, থামো mid = (lo + hi) // 2 # PARTIAL overlap: ভাঙো left = self._query(2 * node + 1, lo, mid, l, r) right = self._query(2 * node + 2, mid + 1, hi, l, r) return left + right class Fenwick: """Fenwick tree (Binary Indexed Tree): update-সহ prefix sums। - add(i, delta): element i += delta O(log n) - prefix_sum(i): element 1..i-এর sum O(log n) - range_sum(l, r): element l..r-এর sum O(log n) IMPORTANT: 1-indexed। Index 0 কখনো ব্যবহার হয় না, কারণ navigation trick `i & (-i)` (lowest set bit) i = 0 হলে 0 দেয়, আর loop-টা চিরকাল ঘুরতে থাকতো। Navigation-এর নিয়ম (পুরো magic-টাই এখানে): * query নিচে নামে: i -= i & (-i) (lowest set bit ছেঁটে ফেলো) * update উপরে ওঠে: i += i & (-i) (পরের covering block-এ লাফাও) Index i "দায়িত্ব নেয়" lowbit(i)-টা element-এর, যারা i-তে শেষ হয়। """ def __init__(self, n): self.n = n self.tree = [0] * (n + 1) # slot 0 অব্যবহৃত def add(self, i, delta): """Element i-তে `delta` যোগ করো (1-indexed)।""" assert 1 <= i <= self.n, "Fenwick is 1-indexed" while i <= self.n: self.tree[i] += delta i += i & (-i) # i-কে ধারণ করা পরের block def prefix_sum(self, i): """Element 1..i-এর sum return করো (1-indexed)। prefix_sum(0) == 0।""" s = 0 while i > 0: s += self.tree[i] i -= i & (-i) # lowest set bit ছাঁটো return s def range_sum(self, l, r): """Element l..r inclusive-এর sum return করো (1-indexed)। কাজ করে কারণ sum invertible: prefix(r) - prefix(l-1)। ঠিক এই inversion-এর জন্যই plain Fenwick range MIN পারে না। """ return self.prefix_sum(r) - self.prefix_sum(l - 1) # --------------------------------------------------------------------------- # Tests আর demo # --------------------------------------------------------------------------- def _brute_range_sum(arr, l, r): """Slow কিন্তু obviously-correct reference — tree দুটো verify করতে ব্যবহার হয়।""" return sum(arr[l:r + 1]) def _test_segment_tree(): data = [2, 5, 1, 4, 9, 3] # notes-এ ব্যবহৃত array-টা st = SegmentTree(data) # পুরো-array আর sub-range query-গুলো brute force-এর সাথে মেলে assert st.query(0, 5) == 24 assert st.query(1, 4) == 19 # walkthrough-এর example assert st.query(2, 2) == 1 # একটা মাত্র element for l in range(len(data)): for r in range(l, len(data)): assert st.query(l, r) == _brute_range_sum(data, l, r) # notes-এর update walkthrough-টা: a[2] = 6 st.update(2, 6) data[2] = 6 assert st.query(0, 5) == 29 assert st.query(1, 4) == 24 for l in range(len(data)): for r in range(l, len(data)): assert st.query(l, r) == _brute_range_sum(data, l, r) # আরও কয়েকটা random-ish update, আবার exhaustively verify করা for i, v in [(0, -7), (5, 100), (3, 0)]: st.update(i, v) data[i] = v for l in range(len(data)): for r in range(l, len(data)): assert st.query(l, r) == _brute_range_sum(data, l, r) def _test_fenwick(): # একই logical array-র উপর একটা Fenwick বানাও (1-indexed) data = [2, 5, 1, 4, 9, 3] n = len(data) fw = Fenwick(n) for i, v in enumerate(data, start=1): # add() দিয়েই build হয়ে যায় fw.add(i, v) assert fw.prefix_sum(0) == 0 assert fw.prefix_sum(6) == 24 assert fw.range_sum(2, 5) == 19 # element 5,1,4,9 for l in range(1, n + 1): for r in range(l, n + 1): assert fw.range_sum(l, r) == _brute_range_sum(data, l - 1, r - 1) # "element 3-কে 6 বানাও"-টা delta হিসেবে লেখা: 6 - current = +5 fw.add(3, 6 - data[2]) data[2] = 6 assert fw.prefix_sum(6) == 29 for l in range(1, n + 1): for r in range(l, n + 1): assert fw.range_sum(l, r) == _brute_range_sum(data, l - 1, r - 1) # notes-এর jump walkthrough-গুলো n = 16-তে consistent big = Fenwick(16) for i in range(1, 17): big.add(i, i) # element i ধরে রাখে value i assert big.prefix_sum(13) == sum(range(1, 14)) # 91, 3-টা hop-এ big.add(5, 10) # 5, 6, 8, 16 ছোঁয় assert big.prefix_sum(4) == 10 # element 5-এর আগে: অপরিবর্তিত assert big.prefix_sum(5) == 25 # 15 + 10 assert big.prefix_sum(16) == sum(range(1, 17)) + 10 def _test_counting_use_case(): # Classic BIT trick: প্রতিটা element-এর ডানে কতগুলো ছোট element, গোনো। # LeetCode "Count of Smaller Numbers After Self"-এর pattern-টাই। arr = [5, 2, 6, 1] fw = Fenwick(max(arr)) # VALUE-গুলোর উপর frequency table counts = [] for v in reversed(arr): # ডান থেকে বাঁয়ে scan করো counts.append(fw.prefix_sum(v - 1)) # v-এর চেয়ে ছোট কয়টা দেখা গেছে fw.add(v, 1) # v-কে seen হিসেবে mark করো counts.reverse() assert counts == [2, 1, 1, 0] if __name__ == "__main__": _test_segment_tree() _test_fenwick() _test_counting_use_case() # -------- markdown walkthrough-গুলোর ছোট্ট demo -------- print("Segment tree on [2, 5, 1, 4, 9, 3]") st = SegmentTree([2, 5, 1, 4, 9, 3]) print(" query(1, 4) =", st.query(1, 4), " (expected 19)") st.update(2, 6) print(" after update(2, 6): query(1, 4) =", st.query(1, 4), " (expected 24)") print("Fenwick tree, n = 16, element i holds value i") fw = Fenwick(16) for i in range(1, 17): fw.add(i, i) print(" prefix_sum(13) =", fw.prefix_sum(13), " (expected 91)") fw.add(5, 10) print(" after add(5, +10): prefix_sum(5) =", fw.prefix_sum(5), " (expected 25)") print("All asserts passed.")