Skip to content

005 — Range Sum Query — Mutable

Source

  • Original source: Classic point-update + range-sum exercise
  • Platform: LeetCode — https://leetcode.com/problems/range-sum-query-mutable/
  • Topic: segment tree and fenwick tree
  • Difficulty: Medium
  • Pattern: segment tree / Fenwick core (point update + range sum)
  • Basic idea inherited from: arrays, recursion

1. Problem in simple words

আবার একটা array আর sumRange(left, right) query — কিন্তু এবার একটা নতুন operation যোগ হয়েছে: update(index, val), যা index-এর element-কে val বানিয়ে দেয়। update আর query যেকোনো order-এ, বহুবার আসতে পারে। এই একটা শব্দ — Mutable — পুরো খেলা বদলে দেয়।

NumArray([1, 3, 5])
sumRange(0, 2)    -> 1 + 3 + 5 = 9
update(1, 2)      -> array এখন [1, 2, 5]
sumRange(0, 2)    -> 1 + 2 + 5 = 8

2. Which basic idea does this inherit from?

এটা arrays আর recursion-এর উপর দাঁড়িয়ে। কিন্তু আসলে এটা problem #1/#2-এর immutable prefix-sum baseline-এর সরাসরি উত্তরসূরি — যেখানে baseline ভেঙে পড়ে, ঠিক সেখান থেকেই এই problem শুরু।

3. What is the hidden math or logic?

লুকানো logic: prefix sums update-এর সাথে যায় না। একটা update prefix array-র পরের প্রতিটা entry stale করে দেয় (../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/-এ দেখা গেছে) — তাই update O(n)। সমাধান: pre-computation-কে এত ছোট টুকরোয় ভাঙো যে একটা update মাত্র O(log n)-টা টুকরো invalid করে। এটাই segment tree / Fenwick-এর central tweak: element নয়, segment-এর answer জমাও।

4. Which data structure is needed?

দুটো পথই খাটে: segment tree (range sum + point update) অথবা Fenwick tree (sum-এর জন্য আরও ছোট code)। যেহেতু এটা plain sum, Fenwick-ই সংক্ষিপ্ততম; কিন্তু segment tree generalize করে (min/max-এও চলে)। নিচে দুটোই দিলাম।

5. Why this data structure fits

Update আর query — দুটোকেই O(log n)-এ দরকার। prefix sums query-তে দ্রুত কিন্তু update-এ O(n); plain array update-এ দ্রুত কিন্তু query-তে O(n)। Tree দুই দিকেই log n দেয়, কারণ একটা leaf মাত্র O(log n)-টা segment-এর ভেতরে থাকে আর প্রতিটা query O(log n)-টা segment জুড়ে তৈরি হয়।

6. Real-life analogy

একটা mall-এর প্রতিটা তলায় বিক্রির running total রাখা আছে, আর প্রতিটা wing-এ wing-total, পুরো mall-এ grand total। একটা দোকানের বিক্রি বদলালে তুমি শুধু ওই দোকান → তার wing → তার তলা → grand total — এই একটা শৃঙ্খলে খবর দাও, পুরো mall নতুন করে গুনতে হয় না। আবার "এই কয়েকটা wing-এর মোট কত" জিজ্ঞেস করলে কয়েকটা wing-total জোড়া দিলেই হয়।

7. Visual explanation

Segment tree-তে update(1, 2) ঠিক একটা root-to-leaf path repair করে (array [1, 3, 5]):

before:                          after update(1, 2):
        [0..2]=9                         [0..2]=8   <- repaired
       /        \                       /        \
   [0..1]=4   [2..2]=5            [0..1]=3   [2..2]=5
   /     \                        /     \
[0..0]=1 [1..1]=3            [0..0]=1 [1..1]=2  <- changed leaf

path touched: [1..1] -> [0..1] -> [0..2]   (3 nodes, O(log n))
সব leaf rebuild করতে হয়নি — শুধু এক শৃঙ্খল।

8. Example input and output

NumArray([1, 3, 5])
  sumRange(0, 2)  -> 9
  update(1, 2)
  sumRange(0, 2)  -> 8

Edge case 1 (একই value-তে update):  update(0, 1) পরে sumRange(0,0) -> 1
Edge case 2 (শেষ element update):    update(2, 10) পরে sumRange(0,2) -> 1+2+10 = 13

9. Brute force thinking

প্রথম সরল চিন্তা: plain array রাখো। update মানে সরাসরি a[index] = val (O(1)); sumRange মানে loop চালিয়ে যোগ (O(n))।

update(i, v): a[i] = v
sumRange(l, r): s = 0; for i in l..r: s += a[i]

10. Why brute force is slow

plain array-তে sumRange প্রতিবার O(n)। উল্টোটা — prefix-sum array রাখলে sumRange O(1) কিন্তু update O(n) (পরের সব prefix stale)। দুটো operation মিশে q-বার এলে দুই ক্ষেত্রেই O(n·q)। LeetCode-এ এটা টাইম-আউট করায়। কোনো plain approach দুটোকে একসাথে দ্রুত করতে পারে না।

11. Key observation

মূল observation: একটা point update পুরো prefix structure ভাঙার দরকার নেই — শুধু কয়েকটা segment। একটা element ঠিক O(log n)-টা segment-এর ভেতরে থাকে (tree-র প্রতি level-এ একটা)। তাই ওই কটা segment-ই repair করো, বাকি সব অক্ষত থাকে।

12. Optimized intuition

Segment tree-তে: leaf set করো, ফেরার পথে প্রতিটা parent re-combine করো — O(log n)। query-তে তিন-ভাগের decision নিয়ে নামো — O(log n)। Fenwick-এ: update মানে delta = val - current[index], তারপর lowbit hop দিয়ে covering block-গুলোয় delta যোগ; sumRange = prefix(r) - prefix(l-1)।

13. Thinking tweak

মোচড়: "update এলে সব আবার হিসাব করতে হবে" — এই ভয় থেকে সরে এসে ভাবো "answer-গুলো এমনভাবে টুকরো করে রাখব যেন একটা update মাত্র এক শৃঙ্খল টুকরোকে ছোঁয়।" Immutable baseline (#1, #2) থেকে এই একটাই বড় লাফ — আর এটাই পুরো folder-এর core।

14. Step-by-step dry run

[1, 3, 5], Fenwick পথে, update(1, 2) তারপর sumRange(0, 2):

  1. শুরুতে Fenwick build: element (1-indexed) 1,2,3 ধরে 1,3,5।
  2. update(1, 2) → 0-indexed 1 = 1-indexed 2। delta = 2 - 3 = -1।
  3. add(2, -1): index 2 → 4 ছোঁয়, ওদের value -1 হয়।
  4. sumRange(0, 2) → prefix(3) - prefix(0) = (1 + 2 + 5) - 0 = 8।
  5. ✓ ঠিক [1, 2, 5]-এর মোট।

15. Python solution

class Fenwick:
    """update-সহ prefix sums, 1-indexed। sum-এর জন্য সংক্ষিপ্ততম structure।"""

    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)

    def add(self, i, delta):                 # element i += delta (1-indexed)
        while i <= self.n:
            self.tree[i] += delta
            i += i & (-i)

    def prefix_sum(self, i):                 # sum of 1..i
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & (-i)
        return s


class NumArray:
    """Mutable range sum — Fenwick দিয়ে। 0-indexed API, ভেতরে 1-indexed BIT।
    point update + range sum দুটোই O(log n)। (sum বলে BIT যথেষ্ট;
    min/max হলে segment tree লাগত।)"""

    def __init__(self, nums):
        self.nums = list(nums)               # set semantics-এর জন্য current value
        self.fw = Fenwick(len(nums))
        for i, v in enumerate(nums):
            self.fw.add(i + 1, v)            # build via adds

    def update(self, index, val):
        delta = val - self.nums[index]       # set = (new - old) যোগ করা
        self.nums[index] = val
        self.fw.add(index + 1, delta)

    def sumRange(self, left, right):         # 0-indexed inclusive
        return self.fw.prefix_sum(right + 1) - self.fw.prefix_sum(left)


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


# ---- tests ----
na = NumArray([1, 3, 5])
assert na.sumRange(0, 2) == 9
na.update(1, 2)
assert na.sumRange(0, 2) == 8                # [1, 2, 5]
na.update(2, 10)
assert na.sumRange(0, 2) == 13              # [1, 2, 10]

# update আর query মিশিয়ে, একটা mirror array-র সাথে exhaustively মেলানো
import random
random.seed(7)
arr = [random.randint(-5, 5) for _ in range(12)]
na = NumArray(arr)
for _ in range(300):
    if random.random() < 0.5:               # random update
        i = random.randrange(len(arr))
        v = random.randint(-5, 5)
        arr[i] = v
        na.update(i, v)
    else:                                    # random range query, brute-checked
        l = random.randrange(len(arr))
        r = random.randrange(l, len(arr))
        assert na.sumRange(l, r) == brute(arr, l, r)

print("সব test pass!")

16. Line-by-line code explanation

  • self.nums = list(nums) — set semantics-এর জন্য current value মনে রাখি, যাতে delta বের করা যায়।
  • update: delta = val - old; BIT শুধু "যোগ" বোঝে, তাই set করতে delta যোগ করি।
  • sumRange: prefix(right+1) - prefix(left) — 0-indexed inclusive থেকে 1-indexed prefix-এ রূপান্তর।
  • brute + random fuzz — update/query মিশিয়ে একটা সরল mirror array-র সাথে মিলিয়ে দেখা।

17. Output walkthrough

NumArray([1,3,5]): sumRange(0,2)=9। update(1,2) delta -1 ঠেলে; sumRange(0,2)=8। update(2,10) পরে 13। তারপর 300 random op-এর fuzz: প্রতিটা query mirror array-র brute sum-এর সাথে মেলে। সব assert pass। শেষে print: সব test pass!।

18. Time complexity

update O(log n), sumRange O(log n) (দুটো prefix call)। Build O(n log n) (n বার add)।

19. Space complexity

O(n) — Fenwick array + current-value array।

20. Common mistakes

  • update-এ delta-র বদলে সরাসরি val add করা — তখন পুরোনো value যোগ থেকে যায়, ভুল।
  • 0-indexed/1-indexed গুলিয়ে ফেলা — sumRange-এ right+1 আর prefix_sum(left) দরকার।
  • Mutable জেনেও plain prefix-sum array ব্যবহার করা — update-এ O(n), টাইম-আউট।

21. Which basic problem this inherits from

ভিত্তি: arrays + recursion, আর সরাসরি #1/#2-এর immutable baseline (../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/)। তফাত একটাই: update যোগ হওয়ায় baseline ভেঙে পড়েছে। গভীর: ../segment-tree.md, ../fenwick-tree.md, ../implementation.py।

22. Similar harder problems

23. Pattern learned

Segment tree / Fenwick core: point update + range sum, দুটোই O(log n)। এই combination-ই পুরো folder-এর মেরুদণ্ড — answer-গুলো segment-এ ভেঙে রাখায় update আর query কোনোটাই আর O(n) থাকে না।

24. Final summary

ভবিষ্যতের আমাকে: "update আছে?" — হ্যাঁ হলে prefix sums বাদ। sum + point update হলে Fenwick (সংক্ষিপ্ততম), fancy কিছু হলে segment tree। মূল মন্ত্র: একটা update যেন মাত্র O(log n)-টা segment ছোঁয়। এই problem-টাই সেই দরজা যেখানে immutable থেকে mutable-এ লাফ দিলাম।

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