002 — Range Sum Query — Immutable¶

Source¶

Original source: Classic prefix-sum exercise (class-based API)
Platform: LeetCode — https://leetcode.com/problems/range-sum-query-immutable/
Topic: segment tree and fenwick tree (baseline — tree লাগে না)
Difficulty: Easy
Pattern: prefix sums baseline, একটা reusable class-এ মোড়া
Basic idea inherited from: math level 5 prefix sums — ../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/

1. Problem in simple words¶

তোমাকে একটা integer array দেওয়া হবে একবার, constructor-এ। তারপর বারবার sumRange(left, right) call আসবে, প্রতিবার তোমাকে left থেকে right (দুই প্রান্ত সহ) sum return করতে হবে। array কখনো বদলায় না — তাই নাম Immutable। আগের problem-এর সাথে পার্থক্য শুধু একটাই: এবার এটা একটা class-based API, free function নয়।

NumArray([-2, 0, 3, -5, 2, -1])
sumRange(0, 2)  ->  -2 + 0 + 3        =  1
sumRange(2, 5)  ->  3 + (-5) + 2 + -1 = -1
sumRange(0, 5)  ->  সব মিলে           = -3

2. Which basic idea does this inherit from?¶

এটাও সরাসরি prefix sums (../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/)। একদম problem #1-এর মতোই — শুধু এখানে data একবার দিয়ে রাখা হয় constructor-এ, আর query method হিসেবে আসে। চিন্তা এক, মোড়ক আলাদা।

3. What is the hidden math or logic?¶

একই invertibility: sum-কে বিয়োগ দিয়ে undo করা যায়। P[i] যদি প্রথম i-টা element-এর মোট হয়, তাহলে sumRange(left, right) = P[right+1] - P[left]। এখানে negative সংখ্যাও আছে, কিন্তু তাতে কিছু যায় আসে না — যোগ-বিয়োগ negative-এও দিব্যি কাজ করে।

4. Which data structure is needed?¶

constructor-এ একবার বানানো একটা prefix-sum array, class-এর ভেতরে রাখা। তারপর প্রতিটা sumRange সেই array থেকে দুটো মান পড়ে বিয়োগ করে।

5. Why this data structure fits¶

API-টা স্পষ্টভাবে বলে দেয় data immutable — কোনো update method নেই। তাই segment tree বা Fenwick tree বানানো নিছক অপচয়। "Constructor-এ একবার pre-compute, তারপর O(1) query" — এটাই এই shape-এর জন্য নিখুঁত ফিট, আর ঠিক prefix sums যা করার জন্য বানানো।

6. Real-life analogy¶

ভাবো তুমি একটা বইয়ের প্রতিটা chapter শেষে "এ পর্যন্ত মোট কত পৃষ্ঠা পড়লে" লিখে রেখেছ। বইটা আর বদলাবে না (immutable)। এবার যে-ই জিজ্ঞেস করুক "chapter 3 থেকে 7 পর্যন্ত কত পৃষ্ঠা", তুমি শুধু "chapter 7-এর শেষে মোট" থেকে "chapter 2-এর শেষে মোট" বিয়োগ করো — পৃষ্ঠা আবার গুনতে হয় না।

7. Visual explanation¶

nums = [-2, 0, 3, -5, 2, -1]-এর prefix array P (sentinel P[0]=0):

index :   0    1    2    3    4    5    6
nums  :       -2    0    3   -5    2   -1
P     :   0   -2   -2    1   -4   -2   -3
              running total (negative-এও ঠিক কাজ করে)

sumRange(2, 5):
        P = [0, -2, -2, 1, -4, -2, -3]
                     ^cut P[2]    ^take P[6]
        = P[right+1] - P[left] = P[6] - P[2] = -3 - (-2) = -1
        (= 3 + (-5) + 2 + (-1), correct)

8. Example input and output¶

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

Edge case 1 (একটা element):   sumRange(3, 3) -> -5
Edge case 2 (পুরো শেষ অংশ):    sumRange(4, 5) -> 2 + (-1) = 1

9. Brute force thinking¶

প্রথম সরল চিন্তা: prefix কিছু না বানিয়ে, প্রতিটা sumRange-এ left থেকে right loop চালিয়ে যোগ করো।

def sumRange(left, right):
    s = 0
    for i in range(left, right + 1):
        s += nums[i]
    return s

10. Why brute force is slow¶

প্রতিটা sumRange call সর্বোচ্চ n-টা element ছোঁয়। যদি q-টা call আসে, মোট খরচ O(n × q)। LeetCode-এ এই call বহুবার আসে বলেই এটা টাইম-আউট ঝুঁকিতে ফেলে। একই range বারবার যোগ করাটা স্পষ্ট অপচয় — যখন একবার pre-compute করেই কাজ চলে।

11. Key observation¶

মূল observation: data immutable, তাই constructor-এ একবার কাজ করে নিলে প্রতিটা query সস্তা হয়ে যায়। sumRange(left, right) = P[right+1] - P[left] — দুটো array-পড়া আর একটা বিয়োগ, ব্যস।

12. Optimized intuition¶

Constructor-এ O(n)-এ prefix array বানাও। তারপর প্রতিটা sumRange O(1)। অনেকগুলো query থাকলেও total খরচ build + queries = O(n + q)। Immutability-ই আমাদের এই pre-computation নিরাপদে cache করতে দেয় — কারণ কখনো invalid হওয়ার ভয় নেই।

13. Thinking tweak¶

মোচড়: "প্রতিবার যোগ করব" থেকে সরে এসে ভাবো "constructor-এ একবার সব checkpoint বসিয়ে দেব, query শুধু দুই checkpoint-এর তফাত পড়বে।" খেয়াল করো — এই immutability ভেঙে যদি update যোগ হতো (#5, #6), prefix array আর চলত না, তখনই segment tree / Fenwick tree-র দরকার পড়ত।

14. Step-by-step dry run¶

nums = [-2, 0, 3, -5, 2, -1], call sumRange(2, 5):

Constructor prefix বানায়: P = [0, -2, -2, 1, -4, -2, -3]
sumRange(2, 5) এসেছে।
P[right+1] = P[6] = -3
P[left] = P[2] = -2
উত্তর = -3 - (-2) = -1 → এটাই 3 + (-5) + 2 + (-1), ঠিক আছে।

15. Python solution¶

class NumArray:
    """Immutable array-র উপর O(1) range sum।
    Constructor-এ একবার prefix sums বানিয়ে রাখি; কোনো update নেই
    বলে tree লাগে না — এটাই দ্রুততম আর সরলতম।"""

    def __init__(self, nums):
        # P[i] = প্রথম i-টা element-এর sum; P[0] = 0 sentinel
        self.P = [0] * (len(nums) + 1)
        for i, v in enumerate(nums):
            self.P[i + 1] = self.P[i] + v

    def sumRange(self, left, right):
        # 0-indexed inclusive [left, right] (LeetCode convention)
        return self.P[right + 1] - self.P[left]


def brute(nums, left, right):
    # 0-indexed inclusive, obviously-correct reference
    return sum(nums[left:right + 1])


# ---- tests ----
nums = [-2, 0, 3, -5, 2, -1]
na = NumArray(nums)

assert na.sumRange(0, 2) == 1       # -2 + 0 + 3
assert na.sumRange(2, 5) == -1      # 3 - 5 + 2 - 1
assert na.sumRange(0, 5) == -3      # পুরো array
assert na.sumRange(3, 3) == -5      # একটা element

# brute force-এর সাথে exhaustively মিলিয়ে দেখা (negative-সহ array)
for left in range(len(nums)):
    for right in range(left, len(nums)):
        assert na.sumRange(left, right) == brute(nums, left, right)

print("সব test pass!")

16. Line-by-line code explanation¶

self.P = [0] * (len(nums) + 1) — n+1 ঘর, P[0]=0 sentinel যাতে left=0-এও P[left] ঠিক থাকে।
self.P[i + 1] = self.P[i] + v — running total, negative value-তেও স্বাভাবিকভাবে কাজ করে।
sumRange(left, right) — P[right+1] - P[left]; LeetCode 0-indexed inclusive বলে right+1।
brute — slow কিন্তু স্পষ্টভাবে সঠিক, fast version-কে verify করার জন্য।

17. Output walkthrough¶

NumArray([-2,0,3,-5,2,-1]) বানায় P = [0,-2,-2,1,-4,-2,-3]। sumRange(0,2) দেয় P[3]-P[0]=1, sumRange(2,5) দেয় P[6]-P[2]=-1 — সব assert pass। double loop সব (left,right)-কে brute-এর সাথে মেলায়। শেষে print: সব test pass!।

18. Time complexity¶

Constructor O(n) (একবার prefix), প্রতি sumRange O(1)। মোট O(n + q)।

19. Space complexity¶

O(n) — class-এর ভেতরে রাখা n+1 ঘরের prefix array।

20. Common mistakes¶

P[right] - P[left] লেখা — right+1 দরকার, নাহলে right নম্বর element বাদ যায়।
প্রতিটা sumRange-এ নতুন করে prefix বানানো — তাহলে আর O(1) থাকে না, constructor-এই একবার বানাতে হয়।
Immutable জেনেও segment tree বানানো — অপ্রয়োজনীয়; update না থাকলে prefix sums-ই যথেষ্ট।

21. Which basic problem this inherits from¶

ভিত্তি: math level 5-এর prefix sums (../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/)। problem #1-এর সাথে যমজ — শুধু class-এর মোড়কে।

22. Similar harder problems¶

Static Range Sum Queries (একই idea, contest free-function style) — https://cses.fi/problemset/task/1646 (এই tracker-এর #1)
Range Sum Query — Mutable (update যোগ হলে tree লাগে) — https://leetcode.com/problems/range-sum-query-mutable/ (#5)
Range Sum Query 2D — Immutable (2D prefix sums) — https://leetcode.com/problems/range-sum-query-2d-immutable/

23. Pattern learned¶

Prefix sums baseline (class API): immutable data-র উপর constructor-এ একবার pre-compute, তারপর O(1) range sum। যেই মুহূর্তে কেউ "update"ও চাইবে, এই baseline ভেঙে পড়বে — আর সেটাই segment tree / Fenwick tree-র দিকে ঠেলে দেবে।

24. Final summary¶

ভবিষ্যতের আমাকে: "Immutable" শব্দটাই সংকেত — কোনো update নেই, তাই prefix sums-ই answer, tree নয়। API class-based হলেও মূল চিন্তা বদলায় না: pre-compute once, subtract per query। পরের দুই-একটা problem (#5, #6)-এ update যোগ হবে, তখন দেখবে কেন এই সরল trick আর টেকে না।

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