068 — Range Sum Query

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

Source

• Original source: Classic range query via prefix sum
• Platform: LeetCode Range Sum Query Immutable — https://leetcode.com/problems/range-sum-query-immutable/, CSES Static Range Sum Queries — https://cses.fi/problemset/task/1646
• Topic: Math-based programming fundamentals → Level 5: Prefix, Difference, Contribution
• Difficulty: Easy
• Pattern: range sum via P[r] - P[l-1]
• Basic idea inherited from: 067 — Prefix Sum

1. Problem in simple words

একটা সংখ্যার 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)-এ দিতে হবে।

2. What is the math idea?

মূল 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" হলো বিয়োগ — তাই এটা কাজ করে।

3. Which basic idea does this inherit from?

সরাসরি 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।

4. Real-life analogy

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

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

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

5. Visual explanation

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-টাই সবচেয়ে বড় ফাঁদ।

6. Example input and 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 একইরকম।

7. Brute force thinking

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

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, প্রতিবার নতুন করে যোগ। ঠিক উত্তরই দেয়।

8. Why brute force may be slow

একটা 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-এর ডাক।

9. Better thinking

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

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 থেকে আকাশ-পাতাল দ্রুত।

10. Thinking tweak

আসল "আহা!" মুহূর্ত: 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।

11. Step-by-step dry run

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-ও ঠিকঠাক।

12. Python solution

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

13. Line-by-line explanation

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

14. Output walkthrough

চালালে:

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

15. Time complexity

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

16. Space complexity

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

17. Common mistakes

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)-এর লাভটাই হারালে।

18. Harder problems that inherit this idea

• LeetCode — Range Sum Query Immutable (https://leetcode.com/problems/range-sum-query-immutable/) — ঠিক এই problem, class-আকারে (NumArray)।
• CSES — Static Range Sum Queries (https://cses.fi/problemset/task/1646) — অনেক query, একই কৌশল।
• LeetCode — Range Sum Query 2D Immutable (https://leetcode.com/problems/range-sum-query-2d-immutable/) — এক dimension থেকে দুই dimension-এ (072)।

19. Pattern learned

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-এ)।

20. Final summary

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