Problem link ও উৎস
- **Original source:** CSES Problem Set — Range Queries section
- **Platform:** CSES —
- **Topic:** segment tree and fenwick tree (warm-up — আসলে tree-ই লাগে না)
- **Difficulty:** Easy
- **Pattern:** prefix sums (frozen array, কোনো update নেই)
- **Basic idea inherited 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)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে `n`-টা সংখ্যার একটা array দেওয়া আছে, আর `q`-টা প্রশ্ন। প্রতিটা প্রশ্নে দুটো index `a` আর `b` দেওয়া থাকে, তোমাকে বলতে হবে `a` থেকে `b` পর্যন্ত (দুই প্রান্ত সহ) সব element-এর **sum** কত। গুরুত্বপূর্ণ ব্যাপার: array কখনো বদলায় না — এটা পুরোপুরি frozen।
```text
array = [3, 2, 4, 5, 1, 1, 5, 3] (1-indexed CSES-এ)
query a=2, b=4 -> 2 + 4 + 5 = 11
query a=5, b=6 -> 1 + 1 = 2
```
### Input ও output {#8-example-input-and-output}
```text
Input:
n = 8, q = 2
array = [3, 2, 4, 5, 1, 1, 5, 3]
query 2 4
query 5 6
Output:
11
2
Edge case 1 (পুরো array): a=1, b=8 -> 24
Edge case 2 (একটা element): a=3, b=3 -> 4
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
একটা দোকানদার ভাবো, যে দিনের শেষে খাতায় চলমান মোট (running total) লিখে রাখে: "1 নম্বর ক্রেতার পর মোট কত, 2 নম্বরের পর কত..."। এবার যে-ই জিজ্ঞেস করুক "3 থেকে 7 নম্বর ক্রেতার মোট কত", সে শুধু "7-এর পর মোট" থেকে "2-এর পর মোট" বিয়োগ করে — খাতা আবার ঘেঁটে যোগ করতে হয় না।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা সরাসরি **prefix sums**-এর উপর দাঁড়িয়ে — তুমি যেটা [../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/](../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/README.md)-এ শিখেছ। মূল চিন্তা ছিল: একই যোগ বারবার না করে, "শুরু থেকে প্রতিটা জায়গা পর্যন্ত মোট" একবার লিখে রাখো, তারপর যেকোনো range-এর sum হয়ে যায় একটা বিয়োগ।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic হলো **invertibility**: sum একটা invertible operation, মানে যোগকে বিয়োগ দিয়ে undo করা যায়। যদি `P[i]` মানে প্রথম `i`-টা element-এর মোট হয়, তাহলে `sum(a..b) = P[b] - P[a-1]`। বাঁ দিকের অপ্রয়োজনীয় অংশটা ঠিক বিয়োগ করে সরিয়ে দিলেই বাকি থাকে যা চাই।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
শুধু **একটা prefix-sum array**। এখানে এই topic-এর নাম "segment tree and fenwick tree" হলেও, এই problem-এ কোনো tree লাগবেই না — কারণ array frozen, কোনো update নেই।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
Tree-গুলোর পুরো অস্তিত্বই **update সামলানোর** জন্য। যখন কোনো update নেই, তখন একটা plain prefix-sum array-ই সবচেয়ে দ্রুত (build O(n), প্রতি query O(1)) আর সবচেয়ে সরল। Frozen array-র উপর segment tree বানানো spirit-এ ভুল উত্তর — pass করলেও over-engineering।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা query-র জন্য `a` থেকে `b` পর্যন্ত একটা loop চালিয়ে যোগ করো।
```text
for each query (a, b):
s = 0
for i in range(a, b+1):
s += array[i]
print(s)
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
প্রতিটা query সর্বোচ্চ `n`-টা element ছোঁয়, আর query আছে `q`-টা — তাই worst case **O(n × q)**। CSES-এ `n` আর `q` দুটোই 2×10^5 পর্যন্ত হতে পারে, মানে প্রায় 4×10^10 operation — অনেক ধীর, time limit exceed করবে। একই অংশ বারবার যোগ করাটাই অপচয়।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **range sum মানেই দুটো prefix sum-এর বিয়োগ**। `sum(a..b)` = (1 থেকে b পর্যন্ত মোট) − (1 থেকে a−1 পর্যন্ত মোট)। একবার সব prefix সাজিয়ে রাখলে, প্রতিটা query একটামাত্র subtraction।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
শুরুতেই একবার O(n)-এ prefix array বানিয়ে নাও। তারপর প্রতিটা query-তে শুধু `P[b] - P[a-1]` return করো — O(1)। মোট খরচ O(n + q), যা brute force-এর O(n × q)-এর তুলনায় আকাশ-পাতাল তফাত।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "প্রতিবার নতুন করে যোগ করব" ভাবার বদলে ভাবো "একবারই সব checkpoint লিখে রাখব, তারপর প্রতিটা উত্তর = দুই checkpoint-এর তফাত।" এই precompute-then-subtract চিন্তাটাই পুরো range-query জগতের ভিত — segment tree আর Fenwick tree এই একই চিন্তাকেই update-সহ্য করার মতো করে বানায়।
### ছবিতে বোঝা {#7-visual-explanation}
`a = [3, 2, 4, 5, 1, 1, 5, 3]`-এর জন্য prefix array `P` (sentinel `P[0]=0` সহ):
```text
index : 0 1 2 3 4 5 6 7 8
a : 3 2 4 5 1 1 5 3
P : 0 3 5 9 14 15 16 21 24
cumulative total up to each position
query a=2, b=4:
P = [0, 3, 5, 9, 14, 15, 16, 21, 24]
^cut here ^take here
sum = P[4] - P[1] = 14 - 3 = 11
(= 2 + 4 + 5, correct)
```
লক্ষ্য করো: কোনো tree নেই, শুধু একটা ফিতা থেকে বাঁ দিকের টুকরো কেটে ফেলা।
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Array `[3, 2, 4, 5, 1, 1, 5, 3]`, query `(2, 4)`:
1. Prefix বানাও: `P = [0, 3, 5, 9, 14, 15, 16, 21, 24]`
2. Query `(a=2, b=4)` এসেছে।
3. `P[b] = P[4] = 14`
4. `P[a-1] = P[1] = 3`
5. উত্তর = `14 - 3 = 11` → এটাই `2 + 4 + 5`, ঠিক আছে।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
class PrefixSum:
"""Frozen array-র জন্য O(1) range sum। কোনো tree লাগে না —
update নেই বলেই plain prefix sums-ই যথেষ্ট আর দ্রুততম।"""
def __init__(self, data):
# P[i] = প্রথম i-টা element-এর sum; P[0] = 0 sentinel
self.P = [0] * (len(data) + 1)
for i, v in enumerate(data):
self.P[i + 1] = self.P[i] + v
def range_sum_1indexed(self, a, b):
# CSES-style: 1-indexed inclusive [a, b]
return self.P[b] - self.P[a - 1]
def brute(data, a, b):
# 1-indexed inclusive, obviously-correct reference
return sum(data[a - 1:b])
# ---- tests ----
data = [3, 2, 4, 5, 1, 1, 5, 3]
ps = PrefixSum(data)
assert ps.range_sum_1indexed(2, 4) == 11 # 2 + 4 + 5
assert ps.range_sum_1indexed(5, 6) == 2 # 1 + 1
assert ps.range_sum_1indexed(1, 8) == 24 # পুরো array
assert ps.range_sum_1indexed(3, 3) == 4 # একটা element
# brute force-এর সাথে exhaustively মিলিয়ে দেখা
for a in range(1, len(data) + 1):
for b in range(a, len(data) + 1):
assert ps.range_sum_1indexed(a, b) == brute(data, a, b)
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `self.P = [0] * (len(data) + 1)` — n+1 ঘরের array, `P[0]=0` sentinel যাতে `a=1`-এও `P[a-1]=P[0]` কাজ করে।
- `self.P[i + 1] = self.P[i] + v` — running total: আগের মোটের সাথে এই element যোগ।
- `range_sum_1indexed(a, b)` — `P[b] - P[a-1]`, একটামাত্র subtraction, O(1)।
- `brute` — slow কিন্তু স্পষ্টভাবে সঠিক reference, যেটা দিয়ে fast version verify করা হয়।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`PrefixSum([3,2,4,5,1,1,5,3])` বানায় `P = [0,3,5,9,14,15,16,21,24]`। `range_sum_1indexed(2,4)` দেয় `14-3=11`, `(5,6)` দেয় `16-14=2` — সব assert pass। double loop সব সম্ভাব্য `(a,b)`-কে brute force-এর সাথে মিলিয়ে দেখে। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**Build O(n)** (একবার prefix array), **প্রতি query O(1)** (একটা subtraction)। মোট **O(n + q)**।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(n)** — শুধু n+1 ঘরের prefix array।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- `P[b] - P[a]` লেখা `P[b] - P[a-1]`-এর বদলে — তাহলে `a` নম্বর element বাদ পড়ে যায়।
- Sentinel `P[0]=0` ভুলে যাওয়া — তখন `a=1`-এ `P[a-1]` index ভুল হয়।
- Frozen array-তে segment tree বানানো — কাজ করবে, কিন্তু অপ্রয়োজনীয়; update না থাকলে tree লাগে না।
## শেখা ও পরের অনুশীলন {#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-then-subtract চিন্তা, কোনো নতুন structure ছাড়াই।
### পরের অনুশীলন {#22-similar-harder-problems}
- Range Sum Query — Immutable (class-based একই idea) —