কনটেন্টে যান

002 — Range Sum Query — Immutable

অধ্যায় · সমস্ত অনুশীলন ও উৎস · ধাপে ধাপে শেখা

Problem link ও উৎস

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

তোমাকে একটা 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

Input ও 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

চেনা উদাহরণে বোঝা

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

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

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

ভেতরের যুক্তি

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

কী দিয়ে তথ্য রাখব

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

এটি কেন উপযুক্ত

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

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

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

উদাহরণ
def sumRange(left, right):
    s = 0
    for i in range(left, right + 1):
        s += nums[i]
    return s

কোথায় বেশি কাজ হচ্ছে

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

যে বিষয়টি খেয়াল করতে হবে

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

আরও কম কাজে সমাধান

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

ভাবনার পরিবর্তন

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

ছবিতে বোঝা

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)

ছোট input-এ ধাপে ধাপে

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

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

কোড ও ব্যাখ্যা

Python

Python
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!")

কোডের প্রতিটি অংশ

  • 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 করার জন্য।

Output মিলিয়ে দেখা

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!।

খরচ ও সাধারণ ভুল

সময়

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

অতিরিক্ত জায়গা

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

যে ভুলগুলো এড়াতে হবে

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

শেখা ও পরের অনুশীলন

ভিত্তির সঙ্গে সম্পর্ক

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

পরের অনুশীলন

কৌশলটি মনে রাখুন

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

নিজেকে যাচাই করুন

ভবিষ্যতের আমাকে: "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।