কনটেন্টে যান

068 — Range Sum Query

067-এ running total বানালে, এবার সেই খাটনির ফসল তুলব। কেউ জিজ্ঞেস করবে "index l থেকে r পর্যন্ত sum কত?" — আর তুমি loop না চালিয়ে, শুধু দুটো prefix value বিয়োগ করে, এক নিমেষে উত্তর দেবে। এই note-এর প্রাণ হলো ফিতা কাটার ছবিটা — কেন P[l-1] বাদ দিতে হয় (l না)। ধীরে পড়ো।

Problem link ও উৎস

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

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

একটা সংখ্যার array a দেওয়া আছে, আর অনেকগুলো query আসবে। প্রতিটা query-তে দুটো index l আর r (l ≤ r) — তোমাকে বলতে হবে a[l] + a[l+1] + ... + a[r] কত (দুই প্রান্ত সহ)।

মুশকিল হলো query অনেক — হয়তো 10^5টা। প্রতিবার l থেকে r পর্যন্ত loop চালালে ধীর হয়ে যাবে। তাই আগে একবার prefix sum বানিয়ে নিয়ে, তারপর প্রতিটা query-র উত্তর O(1)-এ দিতে হবে।

Input ও output

উদাহরণ
a = [2, 5, 1, 3, 4],  P = [0, 2, 7, 8, 11, 15]

query (l, r)  ->  sum         কেন
-----------------------------------------------------
(1, 3)        ->  9           P[4] - P[1] = 11 - 2
(0, 4)        ->  15          P[5] - P[0] = 15 - 0  (পুরো array)
(2, 2)        ->  1           P[3] - P[2] = 8 - 7   (একটাই element)
(0, 0)        ->  2           P[1] - P[0] = 2 - 0
(3, 4)        ->  7           P[5] - P[3] = 15 - 8

Edge case খেয়াল করো: l = r হলে একটাই element-এর sum (নিজেই)। আর l = 0-এর query-তে sentinel P[0] = 0 থাকায় কোনো আলাদা if লাগছে না — formula একইরকম।

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

ভাবো একটা লম্বা রাস্তায় প্রতি কিলোমিটারে একটা মাইলফলক, আর প্রতিটায় লেখা "শুরু (km 0) থেকে এখান পর্যন্ত মোট দূরত্ব"।

তুমি km 3 থেকে km 7 পর্যন্ত দূরত্ব জানতে চাও। প্রতিটা টুকরো আবার মেপো না — শুধু km 7-এর ফলকের সংখ্যা থেকে km 3-এর ফলকের সংখ্যা বিয়োগ করো। যা বাকি থাকে, সেটাই মাঝের অংশ।

prefix array হলো সেই মাইলফলকের সারি, আর range query হলো দুটো ফলকের সংখ্যা বিয়োগ করা। গোটা পথ আবার হাঁটার দরকার নেই।

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

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

সরাসরি 067 (Prefix Sum) থেকে। 067-এ আমরা শিখেছি কীভাবে P[i+1] = P[i] + a[i] দিয়ে running total বানাতে হয়। সেই P array এখানে তৈরি ধরে নিয়ে আমরা শুধু ব্যবহার করছি।

067 ছিল "বানানো", 068 হলো "ব্যবহার করা"। দুটো মিলে prefix sum-এর পূর্ণ গল্প: একবার O(n) খরচ করে precompute, তারপর যত খুশি O(1) query। এই জোড়াই পুরো Level 5-এর core pattern।

ভেতরের অঙ্ক

মূল idea হলো difference of prefix sums (দুই prefix-এর বিয়োগ)। যদি P[i] = প্রথম i টা element-এর মোট হয়, তাহলে:

উদাহরণ
sum(l..r) = P[r+1] - P[l]        (0-indexed, P-র দৈর্ঘ্য n+1)

কেন? P[r+1] = প্রথম (r+1) টার মোট (অর্থাৎ index 0..r), আর P[l] = প্রথম l টার মোট (index 0..l-1)। বড়টা থেকে ছোটটা বিয়োগ করলে শুধু index l থেকে r পর্যন্ত অংশ পড়ে থাকে। যোগের "undo" হলো বিয়োগ — তাই এটা কাজ করে।

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

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

prefix না বানিয়ে, প্রতিটা query-তে সরাসরি loop চালিয়ে যোগ:

Python
def range_sum_brute(a, l, r):
    total = 0
    for i in range(l, r + 1):    # l থেকে r পর্যন্ত (দুই প্রান্ত সহ)
        total += a[i]
    return total

প্রতিটা query-র জন্য আলাদা loop, প্রতিবার নতুন করে যোগ। ঠিক উত্তরই দেয়।

কোথায় বেশি কাজ হতে পারে

একটা query-তে loop চলে (r - l + 1) বার — খারাপ ক্ষেত্রে পুরো array, মানে O(n)। এখন যদি q টা query থাকে, মোট কাজ O(n × q)।

উদাহরণ
n = 100000, q = 100000 হলে:
  brute force: ~10,000,000,000 operation  (O(n·q)) — TLE
  prefix way : ~100,000 (build) + q×O(1)   ≈ 200,000 — চোখের পলকে

অপচয়টা কোথায়? দুটো overlapping query, ধরো (0, 5) আর (0, 6) — প্রায় একই অংশ দুবার যোগ হচ্ছে। একই হিসাব বারবার = precompute-এর ডাক।

আরও ভালোভাবে ভাবা

মূল insight: range sum আসলে দুটো prefix-এর বিয়োগ। একবার prefix P বানিয়ে নাও (O(n)), তারপর প্রতিটা query শুধু একটা বিয়োগ — O(1)।

Python
def build_prefix(a):
    P = [0] * (len(a) + 1)
    for i in range(len(a)):
        P[i + 1] = P[i] + a[i]
    return P

def range_sum(P, l, r):
    return P[r + 1] - P[l]       # O(1)

build একবার, query অসংখ্যবার সস্তায়। n + q-এর মাপে এটা brute force-এর n×q থেকে আকাশ-পাতাল দ্রুত।

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

আসল "আহা!" মুহূর্ত: range sum = বড় prefix − ছোট prefix। যেকোনো রেঞ্জের sum কে দুটো "শুরু থেকে মোট"-এর পার্থক্য হিসেবে দেখা।

আর সূক্ষ্ম tweak-টা off-by-one-এ: বিয়োগ করো P[l] (অর্থাৎ index l-এর আগ পর্যন্ত), যাতে a[l] নিজে থেকে যায়। 0-indexed sentinel convention-এ এটা P[r+1] - P[l]। একটা convention বেছে নিয়ে সবসময় তাতেই থাকো — convention বদলালেই bug।

ছবিতে বোঝা

a = [2, 5, 1, 3, 4], prefix P = [0, 2, 7, 8, 11, 15]। চাই sum(1..3) (index 1, 2, 3 → মান 5, 1, 3)। ছবিটা ফিতা কাটার মতো:

উদাহরণ
a:        [ 2 ]  [ 5 ]  [ 1 ]  [ 3 ]  [ 4 ]
index:      0      1      2      3      4

P[4] = 11  মানে: ┣━━━ প্রথম 4টার মোট (index 0..3) ━━━┫
P[1] = 2   মানে: ┣ index 0 ┫ (এই বাঁ টুকরো বাদ দিতে চাই)

       ┌──── P[4] = 11 ────────────────┐
       [ 2 ][ 5 ][ 1 ][ 3 ]
       └P[1]┘└─── এটুকুই চাই (5+1+3) ──┘

sum(1..3) = P[4] - P[1] = 11 - 2 = 9      (5 + 1 + 3 = 9 ✓)
            = P[r+1] - P[l]   এখানে l=1, r=3

মূল কথা: পুরো বাঁ-অংশ (P[l]) কেটে ফেললে শুধু l থেকে r পড়ে থাকে। বিয়োগ করি P[l] (অর্থাৎ index 0..l-1), P[l+1] না — নইলে a[l] নিজেও কেটে যেত। এই off-by-one-টাই সবচেয়ে বড় ফাঁদ।

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

a = [2, 5, 1, 3, 4], prefix বানানো শেষ: P = [0, 2, 7, 8, 11, 15]। এবার query (1, 3):

  1. শুরুর অবস্থা: l = 1, r = 3, P = [0, 2, 7, 8, 11, 15]
  2. বড় prefix বের করি: P[r+1] = P[4] = 11 (index 0..3-এর মোট)
  3. ছোট prefix বের করি: P[l] = P[1] = 2 (index 0-এর মোট, এটাই বাদ দেব)
  4. বিয়োগ: 11 - 2 = 9
  5. মিলিয়ে দেখি: index 1,2,3 → 5 + 1 + 3 = 9 ✓

আরেকটা, query (2, 2) (একটাই element):

  • P[3] - P[2] = 8 - 7 = 1, আর a[2] = 1 ✓। একটা element-এর range-ও ঠিকঠাক।

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

Python

Python
def build_prefix(a):
    """067-এর prefix build; P[i] = প্রথম i টার মোট, P[0] = 0।"""
    P = [0] * (len(a) + 1)
    for i in range(len(a)):
        P[i + 1] = P[i] + a[i]
    return P


def range_sum(P, l, r):
    """a[l..r] (দুই প্রান্ত সহ)-এর sum, O(1)-এ। P হলো build_prefix-এর ফল।"""
    return P[r + 1] - P[l]


def range_sum_brute(a, l, r):
    """ধীর O(n) per query — শুধু মিলিয়ে দেখার জন্য।"""
    return sum(a[l:r + 1])


# --- ছোট test গুলো (সব pass করা উচিত) ---
a = [2, 5, 1, 3, 4]
P = build_prefix(a)
assert P == [0, 2, 7, 8, 11, 15]

assert range_sum(P, 1, 3) == 9       # 5 + 1 + 3
assert range_sum(P, 0, 4) == 15      # পুরো array
assert range_sum(P, 2, 2) == 1       # একটাই element
assert range_sum(P, 0, 0) == 2       # প্রথম element
assert range_sum(P, 3, 4) == 7       # 3 + 4

# fast আর brute সব (l, r)-এ একই উত্তর দেয় কিনা (brute-force cross-check):
n = len(a)
for l in range(n):
    for r in range(l, n):
        assert range_sum(P, l, r) == range_sum_brute(a, l, r)

# negative array-তেও:
b = [-1, 4, -2, 3]
Pb = build_prefix(b)
for l in range(len(b)):
    for r in range(l, len(b)):
        assert range_sum(Pb, l, r) == sum(b[l:r + 1])

print(range_sum(P, 1, 3))   # 9
print(range_sum(P, 0, 4))   # 15
print("সব test pass!")

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

উদাহরণ
def build_prefix(a):
    ...

067-এর সেই prefix build — running total বানায়। range query-র আগে এটা একবার লাগবেই।

উদাহরণ
def range_sum(P, l, r):
    return P[r + 1] - P[l]

পুরো গল্পের হৃদয়। P[r+1] হলো index 0..r-এর মোট; P[l] হলো index 0..l-1-এর মোট। বিয়োগ করলে বাঁ অংশ কেটে গিয়ে শুধু l..r থাকে। এক বিয়োগ, তাই O(1)।

উদাহরণ
def range_sum_brute(a, l, r):
    return sum(a[l:r + 1])

ধীর version — slice করে যোগ। শুধু fast version মিলিয়ে দেখার জন্য রাখা।

বাকি assert গুলো সব সম্ভাব্য (l, r) জোড়ায় fast আর brute মিলিয়ে দেখছে (nested loop দিয়ে brute-force cross-check), negative array-তেও। সব মিললে সব test pass!।

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

চালালে:

  • range_sum(P, 1, 3) → P[4] - P[1] = 11 - 2 = 9 → প্রথম print ছাপে 9
  • range_sum(P, 0, 4) → P[5] - P[0] = 15 - 0 = 15 → দ্বিতীয় print ছাপে 15
  • সব assert (একক query + nested cross-check) চুপচাপ pass
  • শেষে সব test pass!

ছাপা output:

উদাহরণ
9
15
সব test pass!

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

সময়

Build O(n) (একবার), per query O(1) (একটা বিয়োগ)। মোট q টা query-তে O(n + q)। brute force-এর O(n × q)-এর তুলনায় বিশাল লাভ — query যত বেশি, তত বেশি লাভ।

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

O(n) — prefix array P রাখতে n+1 ঘর। query করতে আর কোনো বাড়তি জায়গা লাগে না, শুধু গুটিকয় variable (O(1) per query)।

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

  1. P[r] - P[l-1] আর P[r+1] - P[l] গুলিয়ে ফেলা — দুটো ভিন্ন convention (1-indexed vs sentinel 0-indexed)। একটা বেছে নিয়ে সবসময় তাতেই থাকো।
  2. P[r+1] - P[l-1] লেখা — তাহলে a[l-1]-ও যোগ হয়ে যায় (বেশি)। sentinel convention-এ সঠিক হলো P[r+1] - P[l]।
  3. P[r] - P[l] লেখা — তাহলে a[r] নিজে বাদ পড়ে (কম)। r+1 দরকার কারণ rrange দুই প্রান্ত সহ।
  4. l = 0-এর জন্য আলাদা if লেখা — sentinel P[0] = 0 থাকলে দরকার নেই; formula তখন সব l-এ এক।
  5. প্রতিবার slice/loop চালানো — prefix বানিয়ে রাখার পরেও যদি sum(a[l:r+1]) করো, তাহলে O(1)-এর লাভটাই হারালে।

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

এই ধারণার পরের অনুশীলন

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

Range sum via prefix difference — sum(l..r) = P[r+1] - P[l]। বড় শিক্ষা: যেকোনো রেঞ্জের যোগফল = দুটো "শুরু থেকে মোট"-এর বিয়োগ; precompute একবার, query অসংখ্যবার সস্তায়। off-by-one-এ সাবধান — P[l] বাদ, P[l-1] না (sentinel convention-এ)।

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

ভবিষ্যতের আমাকে এক লাইনে: "range sum = P[r+1] - P[l] (sentinel 0-indexed)। বড় prefix থেকে ছোট prefix বিয়োগ, বাঁ অংশ কেটে যায়। build O(n), query O(1) — অনেক query থাকলেই এই pattern।"

পরের ধাপ → 069 — Difference Array (এবার উল্টো দিক: query নয়, range update)।

ফিরে দেখা: শিকড় → 067 — Prefix Sum · এই level-এর map → ../README.md · concept ঝালাই → ../concept-notes.md · template → ../../../templates/math-problem-note-template.md।

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