006 — Dynamic Range Sum Queries¶

Source¶

Original source: CSES Problem Set — Range Queries section
Platform: CSES — https://cses.fi/problemset/task/1648
Topic: segment tree and fenwick tree
Difficulty: Medium
Pattern: segment tree / Fenwick core (point update + range sum, contest scale)
Basic idea inherited from: arrays, recursion

1. Problem in simple words¶

n-টা সংখ্যার একটা array, আর q-টা operation। প্রতিটা operation দুই রকমের একটা:

type 1:  "k u"   ->  index k-এর value u বানাও  (update)
type 2:  "a b"   ->  index a থেকে b পর্যন্ত sum বলো  (range sum)

এটা ঠিক LeetCode 307-এরই contest সংস্করণ — শুধু এখানে n আর q বড় (2×10^5 পর্যন্ত), তাই O(log n) সমাধান বাধ্যতামূলক, আর input দ্রুত পড়তে হয়।

2. Which basic idea does this inherit from?¶

এটা arrays আর recursion-এর উপর দাঁড়িয়ে, আর সরাসরি problem #5 (Range Sum Query — Mutable)-এর উত্তরসূরি। সেখানে শেখা point-update + range-sum reflex-টাই এখানে contest scale-এ পরীক্ষা হয়।

3. What is the hidden math or logic?¶

একই central tweak: update prefix sums ভেঙে দেয় (../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/), তাই answer-গুলো segment-এ ভেঙে রাখো। তখন একটা update মাত্র O(log n)-টা segment-কে invalid করে, আর যেকোনো range query সর্বোচ্চ O(log n)-টা ready segment দিয়ে tile হয়।

4. Which data structure is needed?¶

segment tree বা Fenwick tree — দুটোই চলে (plain sum)। নিচে একটা segment tree দিলাম, কারণ #5-এ Fenwick দেখানো হয়েছে; এখানে দুই structure-ই পরিচিত হওয়া ভালো। Fenwick হলে code আরও ছোট হতো।

5. Why this data structure fits¶

contest constraint বলে দেয়: 2×10^5 update + 2×10^5 query। O(n) per op মানে ~4×10^10 — অসম্ভব। Tree প্রতিটাকে O(log n)-এ নামায় (~18 step), মোট ~q·log n ≈ কয়েক মিলিয়ন — অনায়াসে time limit-এর ভেতরে।

6. Real-life analogy¶

ভাবো একটা বড় warehouse-এর প্রতিটা shelf-এ stock-count, প্রতিটা aisle-এ aisle-total, পুরো warehouse-এ grand total লেখা। একটা shelf-এর stock বদলালে শুধু shelf → aisle → warehouse — এই শৃঙ্খলে সংখ্যা আপডেট করো। "এই কয়েকটা aisle-এ মোট কত stock" জিজ্ঞেস করলে কয়েকটা aisle-total জোড়া দিলেই উত্তর — হাজার hাজার shelf আলাদা করে গুনতে হয় না।

7. Visual explanation¶

Segment tree-তে query একটা range-কে কয়েকটা ready node-এ ভাঙে; update এক শৃঙ্খল repair করে (array [2, 5, 1, 4, 9, 3]):

                      [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

query(1, 4): take [1..1]=5, [2..2]=1, [3..4]=13  -> 19   (3 ready pieces)
update(2, v): repair path [2..2] -> [0..2] -> [0..5]      (3 nodes)

8. Example input and output¶

n = 8, q = 4
array = [3, 2, 4, 5, 1, 1, 5, 3]
  2 1 4   ->  sum a[1..4] = 3 + 2 + 4 + 5 = 14
  1 3 9   ->  set a[3] = 9   (array: [3, 2, 9, 5, ...])
  2 1 4   ->  sum a[1..4] = 3 + 2 + 9 + 5 = 19
  2 5 6   ->  sum a[5..6] = 1 + 1 = 2

Output:
  14
  19
  2

9. Brute force thinking¶

প্রথম সরল চিন্তা: plain array; update মানে a[k]=u (O(1)), range sum মানে loop (O(n))। অথবা prefix-sum array: query O(1) কিন্তু প্রতি update-এ পুরো prefix rebuild (O(n))।

update: a[k] = u
query : s = 0; for i in a..b: s += a[i]

10. Why brute force is slow¶

contest scale-এ q ≈ 2×10^5, n ≈ 2×10^5। plain array-এ query O(n), prefix-array-এ update O(n) — দুই ক্ষেত্রেই worst case ~4×10^10 operation, যা কয়েক সেকেন্ডের সীমা বহুগুণ ছাড়িয়ে যায়। তাই brute সরাসরি TLE।

11. Key observation¶

মূল observation: এটা একদম #5, শুধু বড়। যেহেতু update আর query মেশানো, কোনো একটাকে O(n) রাখা যাবে না — দুটোকেই O(log n)-এ নামাতে হবে। Tree (বা BIT) ঠিক সেটাই করে: answer segment-এ ভাঙা থাকায় update কয়েকটা segment ছোঁয়, query কয়েকটা segment জোড়ে।

12. Optimized intuition¶

একবার O(n)-এ tree build করো। প্রতিটা type-1 হলে leaf set + path repair (O(log n)); প্রতিটা type-2 হলে তিন-ভাগের descent (O(log n))। Input বড় বলে দ্রুত I/O ব্যবহার করো (একবারে সব পড়ে নাও) — নইলে structure ঠিক থাকলেও parsing-এ TLE হতে পারে।

13. Thinking tweak¶

মোচড়: contest-এ সবচেয়ে আগে এক লাইনে সিদ্ধান্ত নাও — "prefix, Fenwick, না segment tree, আর কেন?"। এখানে: update আছে + শুধু sum → Fenwick সংক্ষিপ্ততম, কিন্তু segment tree-ও চলে। ভুল সিদ্ধান্ত (যেমন static array ভেবে prefix) এখানে wrong answer, type করার আগেই ধরা চাই।

14. Step-by-step dry run¶

[3, 2, 4, 5, 1, 1, 5, 3] (0-indexed ভেতরে), op set index 2 = 9 তারপর sum [0..3]:

Build: root [0..7] = 24।
update(2, 9): leaf [2..2] = 9; ফেরার পথে [2..3], [0..3], [0..7] repair।
query(0, 3): [0..1] ভেতরে (take), [2..3] ভেতরে (take) → তাদের sum।
মান = (3+2) + (9+5) = 5 + 14 = 19। ✓
কোনো rebuild হয়নি — শুধু এক শৃঙ্খল repair, কয়েক টুকরো জোড়া।

15. Python solution¶

class SegmentTree:
    """RANGE SUM + POINT UPDATE। Element নয়, SEGMENT-এর answer জমায়।
    Flat list, heap layout: node i -> 2i+1 (বাঁ), 2i+2 (ডান)। Size 4n safe।
    build O(n), query/update O(log n)। 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:
            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 update(self, i, value):                   # set a[i] = value (0-indexed)
        self._update(0, 0, self.n - 1, i, value)

    def _update(self, node, lo, hi, i, value):
        if lo == hi:
            self.tree[node] = value
            return
        mid = (lo + hi) // 2
        if i <= mid:
            self._update(2 * node + 1, lo, mid, i, value)
        else:
            self._update(2 * node + 2, mid + 1, hi, i, value)
        self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2]

    def query(self, l, r):                         # sum of [l, r] inclusive
        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
        if l <= lo and hi <= r:                    # পুরো ভেতরে
            return self.tree[node]
        mid = (lo + hi) // 2                        # আংশিক: ভাঙো
        return (self._query(2 * node + 1, lo, mid, l, r) +
                self._query(2 * node + 2, mid + 1, hi, l, r))


def brute(arr, l, r):
    return sum(arr[l:r + 1])


# ---- tests ----
data = [3, 2, 4, 5, 1, 1, 5, 3]
st = SegmentTree(data)

assert st.query(0, 3) == 14                  # 3+2+4+5
st.update(2, 9)                              # index 2 -> 9 (1-indexed 3)
data[2] = 9
assert st.query(0, 3) == 19                  # 3+2+9+5
assert st.query(4, 5) == 2                   # 1+1

# update আর query মিশিয়ে, mirror array-র সাথে exhaustively যাচাই
import random
random.seed(11)
arr = [random.randint(0, 9) for _ in range(20)]
st = SegmentTree(arr)
for _ in range(500):
    if random.random() < 0.5:
        i = random.randrange(len(arr))
        v = random.randint(0, 9)
        arr[i] = v
        st.update(i, v)
    else:
        l = random.randrange(len(arr))
        r = random.randrange(l, len(arr))
        assert st.query(l, r) == brute(arr, l, r)

print("সব test pass!")

16. Line-by-line code explanation¶

_build leaf-এ element বসায়, parent = বাঁ + ডান child।
_update target leaf set করে, ফেরার পথে প্রতিটা parent re-combine — এক শৃঙ্খল।
_query তিন-ভাগের decision: বাইরে 0, ভেতরে ready sum, আংশিক দুই child যোগ।
brute + random fuzz — update/query মিশিয়ে mirror array-র সাথে মিলিয়ে দেখা।

17. Output walkthrough¶

SegmentTree([3,2,4,5,1,1,5,3]): query(0,3)=14। update(2,9)-এর পর query(0,3)=19, query(4,5)=2। তারপর 500 random op fuzz: প্রতিটা query mirror brute-এর সাথে মেলে। সব assert pass। শেষে print: সব test pass!।

18. Time complexity¶

Build O(n), update O(log n), query O(log n)। মোট O(n + q log n)।

19. Space complexity¶

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

20. Common mistakes¶

contest-এ ধীর input পড়া (লাইনে লাইনে) — structure ঠিক হলেও parsing-এ TLE; একবারে সব পড়ো।
1-indexed (CSES) আর 0-indexed (code) গুলিয়ে ফেলা — index shift মনে রাখো।
Static ভেবে prefix sums বানানো — update আছে, তাই ভুল; decision drill আগে করো।

21. Which basic problem this inherits from¶

ভিত্তি: arrays + recursion, আর সরাসরি #5 (Range Sum Query — Mutable)। baseline-এর ব্যর্থতা (#1, #2-এর prefix sums update-এ ভাঙে) থেকেই এর জন্ম। গভীর: ../segment-tree.md, ../implementation.py।

22. Similar harder problems¶

Dynamic Range Minimum Queries (sum-এর বদলে min — Fenwick এখানে চলবে না) — CSES "Dynamic Range Minimum Queries" (এই tracker-এর #7)
Range Xor Queries (static, invertible op) — CSES "Range Xor Queries" (#8)
Hotel Queries (max tree বেয়ে নামা) — CSES "Hotel Queries" (#15)

23. Pattern learned¶

Segment tree / Fenwick core (contest scale): point update + range sum, দুটোই O(log n), বড় input-এও। এই milestone-এর পর যেকোনো "sum with updates" problem দেখা মাত্র সমাধান করতে পারা উচিত।

24. Final summary¶

ভবিষ্যতের আমাকে: এটাই সেই milestone problem — "sum + update" দেখলেই হাত আপনাআপনি Fenwick বা segment tree-তে যাবে। Contest-এ আগে এক লাইনে structure-choice লেখো, তারপর দ্রুত I/O, তারপর O(log n) op। ভিতটা #5-এর সাথে অভিন্ন; এখানে শুধু scale বড় হলো।

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