009 — Static Range Sum Queries¶

Source¶

Original source: Classic prefix-sum exercise
Platform: CSES Problem Set — task "Static Range Sum Queries" — https://cses.fi/problemset/
Topic: array / prefix sums
Difficulty: Easy
Pattern: prefix sums (একবার precompute, প্রতিটা query O(1))
Basic idea inherited from: math level 5-এর prefix sums, সরাসরি — "প্রথম i-টা element-এর যোগফল আগে থেকে জমিয়ে রাখা"

1. Problem in simple words¶

একটা static (কখনো বদলায় না) integer array দেওয়া, আর অনেকগুলো query। প্রতিটা query-তে দুটো index l আর r দেওয়া হয় (1-indexed, দুই প্রান্ত inclusive); তোমাকে l থেকে r পর্যন্ত সব element-এর যোগফল বলতে হবে। query-র সংখ্যা অনেক বেশি হতে পারে, তাই প্রতিবার নতুন করে যোগ করলে চলবে না।

arr = [1, 2, 3, 4, 5]   (1-indexed)
query (2, 4) -> 2 + 3 + 4 = 9
query (1, 5) -> পুরোটা = 15

2. Which basic idea does this inherit from?¶

এটা math chapter-এর prefix sums একদম সরাসরি reuse করে: আগে থেকে prefix[i] = প্রথম i-টা element-এর যোগফল হিসাব করে রাখো, তাহলে যেকোনো range-এর যোগফল নেমে আসে একটা বিয়োগে। পুরো derivation আর difference-array জমজটার জন্য দেখো ../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/।

3. What is the hidden math or logic?¶

লুকানো logic একটা telescoping (পরপর বাতিল হওয়া) সম্পর্ক: sum(l..r) = prefix[r] - prefix[l-1]। কারণ prefix[r]-এ আছে 1..r-এর সব, আর prefix[l-1]-এ আছে 1..l-1-এর সব; বিয়োগ করলে শুধু l..r-টুকু টিকে থাকে। তাই query-প্রতি কাজ O(1)।

4. Which data structure is needed?¶

একটা prefix-sum array prefix, যার সাইজ n+1। prefix[0] = 0 (কিছুই যোগ হয়নি) আর prefix[i] = arr[0] + ... + arr[i-1]। এই একটা extra array-ই যথেষ্ট।

5. Why this data structure fits¶

Array-র O(1) random access-এর কারণে prefix[r] আর prefix[l-1] দুটোতেই সরাসরি পৌঁছানো যায় (concept.md-র mailbox analogy)। একবার O(n) খরচে prefix বানিয়ে নিলে, এরপর যত query-ই আসুক প্রতিটা O(1) — এটাই "precompute once, answer fast" idea।

6. Real-life analogy¶

ভাবো একটা দৌড়ের ট্র্যাকে প্রতিটা মাইলফলকে লেখা আছে "শুরু থেকে এ পর্যন্ত মোট কত মিটার"। কেউ যদি জিজ্ঞাসা করে "3 নম্বর থেকে 7 নম্বর মাইলফলকের দূরত্ব কত?" — তুমি দুটো লেখা পড়ে বিয়োগ করো, পুরো পথ আবার মাপতে হয় না।

7. Visual explanation¶

arr = [1, 2, 3, 4, 5] দিয়ে prefix বানানো আর একটা query:

index :   0   1   2   3   4   5
arr   :       1   2   3   4   5
prefix:   0   1   3   6  10  15
              ^               ^
prefix[i] = prefix[i-1] + arr[i-1]

query (2, 4) = prefix[4] - prefix[1] = 10 - 1 = 9
                 (1..4 মোট)  (1..1 মোট)   ফল

8. Example input and output¶

arr = [1, 2, 3, 4, 5]
query (2, 4) -> 9
query (1, 5) -> 15
query (3, 3) -> 3        (একটা ঘর)

Edge case 1 (একটাই element): arr=[7], query (1,1) -> 7
Edge case 2 (পুরো array):    query (1, n)         -> মোট যোগফল

9. Brute force thinking¶

প্রথম সরল চিন্তা: প্রতিটা query এলে l থেকে r পর্যন্t একটা loop চালিয়ে যোগ করো।

for each query (l, r):
    s = 0
    for i = l to r:
        s += arr[i]
    output s

10. Why brute force is slow¶

একটা query-তেই O(n) লাগতে পারে; q-টা query থাকলে মোট O(n * q)। CSES-এ n আর q দুটোই দুই লক্ষ পর্যন্ত — তখন এটা চার হাজার কোটি operation, time limit ছাড়িয়ে যাবে। একই overlap বারবার যোগ হচ্ছে, অথচ একবার জমিয়ে রাখলেই হতো।

11. Key observation¶

মূল observation: array যেহেতু static, prefix sum গুলো একবার হিসাব করে রাখলে আর কখনো বদলাতে হয় না। তখন প্রতিটা range sum = দুটো precomputed সংখ্যার বিয়োগ — query যতই আসুক, প্রতিটা ধ্রুব সময়ে।

12. Optimized intuition¶

একবার বাঁ থেকে ডানে হেঁটে prefix array ভরো (O(n))। তারপর প্রতিটা query (l, r)-এর উত্তর prefix[r] - prefix[l-1]। prefix[0]=0 রাখায় l=1 হলেও prefix[0] বিয়োগ করে সুন্দরভাবে কাজ করে — আলাদা special case লাগে না।

13. Thinking tweak¶

মোচড়: "প্রতিবার যোগ করব" ভাবার বদলে ভাবো "শুরু থেকে চলমান যোগফল একবার জমিয়ে নেব, তারপর যেকোনো অংশ = দুই প্রান্তের জমার বিয়োগ।" এই এক চিন্তাই O(n*q)-কে O(n+q) বানিয়ে দেয়।

14. Step-by-step dry run¶

arr = [1, 2, 3, 4, 5], query (2, 4):

prefix বানাই: prefix = [0]; তারপর 0+1=1, 1+2=3, 3+3=6, 6+4=10, 10+5=15 → prefix = [0,1,3,6,10,15]।
query (2, 4): উত্তর = prefix[4] - prefix[2-1] = prefix[4] - prefix[1]।
= 10 - 1 = 9।
ফল: 9 (অর্থাৎ 2 + 3 + 4)।

15. Python solution¶

def range_sums(arr, queries):
    n = len(arr)
    prefix = [0] * (n + 1)               # prefix[i] = arr[0..i-1]-এর যোগফল
    for i in range(1, n + 1):
        prefix[i] = prefix[i - 1] + arr[i - 1]
    answers = []
    for l, r in queries:                 # 1-indexed, দুই প্রান্ত inclusive
        answers.append(prefix[r] - prefix[l - 1])
    return answers

# ---- tests ----
assert range_sums([1, 2, 3, 4, 5], [(2, 4)]) == [9]       # 2+3+4
assert range_sums([1, 2, 3, 4, 5], [(1, 5)]) == [15]      # পুরোটা
assert range_sums([1, 2, 3, 4, 5], [(3, 3)]) == [3]       # একটা ঘর
assert range_sums([1, 2, 3, 4, 5], [(2, 4), (1, 1), (1, 5)]) == [9, 1, 15]
assert range_sums([7], [(1, 1)]) == [7]                   # একটাই element
print("সব test pass!")

16. Line-by-line code explanation¶

prefix = [0] * (n + 1) — n+1 সাইজ, যাতে prefix[0]=0 (খালি prefix) ধরা থাকে।
for i in range(1, n + 1) — 1 থেকে n পর্যন্ত, যাতে prefix[i]-তে প্রথম i-টা element-এর যোগফল বসে।
prefix[i] = prefix[i-1] + arr[i-1] — আগের চলমান যোগফলের সাথে নতুন element যোগ।
for l, r in queries — প্রতিটা query-র দুই প্রান্ত নিই।
prefix[r] - prefix[l-1] — range sum-এর telescoping সূত্র; l=1 হলে prefix[0]=0 বিয়োগ হয়, তাই নিরাপদ।

17. Output walkthrough¶

[1,2,3,4,5]-এর prefix [0,1,3,6,10,15]। (2,4) → 10−1 = 9; (1,5) → 15−0 = 15; (3,3) → 6−3 = 3; multi-query সবগুলো একসাথে [9,1,15]; [7]-এ (1,1) → 7−0 = 7। সব assert pass; শেষে print: সব test pass!।

18. Time complexity¶

O(n + q) — prefix বানাতে O(n), তারপর প্রতিটা query O(1), মোট q-টা query-তে O(q)।

19. Space complexity¶

O(n) — n+1 সাইজের একটা prefix array। query-র উত্তর জমাতে আরও O(q), কিন্তু core structure O(n)।

20. Common mistakes¶

prefix[r] - prefix[l] লেখা — তখন arr[l] (1-indexed l-তম element) বাদ পড়ে যায়; সঠিক হলো prefix[l-1] বিয়োগ।
0-indexed আর 1-indexed গুলিয়ে ফেলা — CSES query 1-indexed; code-এ arr[i-1] দিয়ে সেই shift সামলানো।
prefix-এর সাইজ n রাখা (n+1 নয়) — তখন prefix[0]=0 রাখার জায়গা থাকে না, edge query ভেঙে যায়।

21. Which basic problem this inherits from¶

ভিত্তি: math level 5-এর prefix sums (../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/)। এই একই precompute Subarray Sum Equals K (#15) আর Product Except Self (#14)-এও ফিরে আসে। chapter-এর ../patterns.md-এর "Pattern 3 — Prefix Sums" দেখো।

22. Similar harder problems¶

Subarray Sum Equals K (prefix sum + hash map) — https://leetcode.com/problems/subarray-sum-equals-k/ (#15)
Range Sum Query — Immutable (একই idea, LeetCode-এ) — https://leetcode.com/problems/range-sum-query-immutable/
Range Sum Query 2D — Immutable (2D prefix) — https://leetcode.com/problems/range-sum-query-2d-immutable/

23. Pattern learned¶

Prefix sums: static array-তে "many range-sum queries" দেখলে একবার O(n) precompute, তারপর প্রতিটা উত্তর O(1) বিয়োগ। range/cumulative প্রশ্নের প্রথম হাতিয়ার।

24. Final summary¶

ভবিষ্যতের আমাকে: "range sum = prefix[r] − prefix[l−1]; একবার জমাও, বারবার বিয়োগে উত্তর দাও।" "static array + অনেক range query" দেখলেই prefix-sum array মনে করবে — O(n+q), query-প্রতি O(1)।

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