Problem link ও উৎস
- **Original source:** Classic prefix-sum exercise
- **Platform:** CSES Problem Set — task "Static Range Sum Queries" —
- **Topic:** array / prefix sums
- **Difficulty:** Easy
- **Pattern:** prefix sums (একবার precompute, প্রতিটা query O(1))
- **Basic idea inherited from:** math level 5-এর prefix sums, সরাসরি — "প্রথম i-টা element-এর যোগফল আগে থেকে জমিয়ে রাখা"
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা **static** (কখনো বদলায় না) integer array দেওয়া, আর অনেকগুলো query। প্রতিটা query-তে দুটো index `l` আর `r` দেওয়া হয় (1-indexed, দুই প্রান্ত inclusive); তোমাকে `l` থেকে `r` পর্যন্ত সব element-এর যোগফল বলতে হবে। query-র সংখ্যা অনেক বেশি হতে পারে, তাই প্রতিবার নতুন করে যোগ করলে চলবে না।
```text
arr = [1, 2, 3, 4, 5] (1-indexed)
query (2, 4) -> 2 + 3 + 4 = 9
query (1, 5) -> পুরোটা = 15
```
### Input ও output {#8-example-input-and-output}
```text
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) -> মোট যোগফল
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো একটা দৌড়ের ট্র্যাকে প্রতিটা মাইলফলকে লেখা আছে "শুরু থেকে এ পর্যন্ত মোট কত মিটার"। কেউ যদি জিজ্ঞাসা করে "3 নম্বর থেকে 7 নম্বর মাইলফলকের দূরত্ব কত?" — তুমি দুটো লেখা পড়ে বিয়োগ করো, পুরো পথ আবার মাপতে হয় না।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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/](../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/README.md)।
### ভেতরের যুক্তি {#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।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা query এলে `l` থেকে `r` পর্যন্t একটা loop চালিয়ে যোগ করো।
```text
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) বানিয়ে দেয়।
### ছবিতে বোঝা {#7-visual-explanation}
`arr = [1, 2, 3, 4, 5]` দিয়ে prefix বানানো আর একটা query:
```text
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 মোট) ফল
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`arr = [1, 2, 3, 4, 5]`, query `(2, 4)`:
1. 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]`।
2. query `(2, 4)`: উত্তর = `prefix[4] - prefix[2-1]` = `prefix[4] - prefix[1]`।
3. = `10 - 1 = 9`।
4. ফল: `9` (অর্থাৎ `2 + 3 + 4`)।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
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` বিয়োগ হয়, তাই নিরাপদ।
### Output মিলিয়ে দেখা {#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!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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 ভেঙে যায়।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: math level 5-এর prefix sums ([../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/](../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/README.md))। এই একই precompute Subarray Sum Equals K (#15) আর Product Except Self (#14)-এও ফিরে আসে। chapter-এর [../patterns.md](../patterns.md)-এর "Pattern 3 — Prefix Sums" দেখো।
### পরের অনুশীলন {#22-similar-harder-problems}
- Subarray Sum Equals K (prefix sum + hash map) —