Problem link ও উৎস
- **Original source:** Classic exercise (difference array + prefix query pipeline)
- **Platform:** Classic exercise —
- **Topic:** Math-based programming fundamentals → Level 5: Prefix, Difference, Contribution
- **Difficulty:** Medium
- **Pattern:** difference array (update) + prefix sum (query)
- **Basic idea inherited from:** 069 — Difference Array
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা array `a` (শুরুতে সব 0, দৈর্ঘ্য n)। দুই ধরনের কাজ আসবে:
- **Update:** "index `l` থেকে `r` পর্যন্ত সবার সাথে `x` যোগ করো।"
- **Query:** "index `ql` থেকে `qr` পর্যন্ত sum কত?"
তবে একটা শর্ত: **সব update আগে আসে, তারপর সব query।** (মাঝখানে মেশে না।) তোমার কাজ — সব update দ্রুত প্রয়োগ করে চূড়ান্ত array বানানো, তারপর প্রতিটা query-র sum দ্রুত (O(1)) দেওয়া।
মানে দুটো কৌশল জোড়া লাগানো: update-এর জন্য difference array (069), query-র জন্য prefix sum (067-068)।
### Input ও output {#6-example-input-and-output}
```text
n = 5
updates = [(0, 2, 3), (1, 4, 2)]
final a = [3, 5, 5, 2, 2]
queries:
(1, 3) -> 12 (5 + 5 + 2)
(0, 4) -> 17 (পুরো array)
(2, 2) -> 5 (একটাই element)
(0, 0) -> 3
edge: কোনো update নেই, n = 3 -> a = [0, 0, 0], যেকোনো query -> 0
edge: update (2, 2, 7) শেষ index -> a = [0, 0, 7], query (0, 2) -> 7
```
খেয়াল করো: update আর query-র off-by-one আলাদা আলাদা সামলাতে হয় — update-এ `diff[r+1] -= x`, query-তে `P[qr+1] - P[ql]`। দুটো convention এক না করে গুলিয়ে ফেললেই bug।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো একটা দোকানের stock register। সকালে নানা supplier মাল দিয়ে যায় — "shelf 1 থেকে 3-এ প্রতিটায় 10টা করে যোগ করো", "shelf 2 থেকে 4-এ 5টা করে"। এগুলো সব **update**, আর তুমি ছোট্ট স্লিপে দুই প্রান্তে দাগ দিয়ে রাখো (069-এর সাইনবোর্ড)।
দুপুরে সব মাল গুছিয়ে register-এ লিখে ফেলো (prefix চালিয়ে final stock)। বিকেলে manager আসে নানা প্রশ্ন নিয়ে — "shelf 1 থেকে 3-এ মোট কতটা মাল?" এগুলো **query**, আর তুমি running-total কলাম থেকে দুটো সংখ্যা বিয়োগ করে চটপট উত্তর দাও (068)।
সকালের কাজ (update) আর বিকেলের প্রশ্ন (query) আলাদা — মাঝে একবার গুছিয়ে নাও। এই "আগে সব বদল, তারপর সব প্রশ্ন" ক্রমটাই pipeline-এর প্রাণ।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
মূলত **069 (Difference Array)** থেকে — সেখানকার update pipeline-টা এখানে পর্যায় 1 ও 2। তার উপর **067-068**-এর range query পর্যায় 3-এ যোগ হয়।
069 ছিল "update করে final array পাও"। 070 হলো "তারপর সেই array-তে query-ও করো"। তাই 070 = 069 + 068 — তিনটা idea-র সম্মিলন। এই কারণেই এটা Level 5-এর মাঝামাঝি একটা সুন্দর mile-marker: এক problem-এ সব ঝালাই হয়ে যায়।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
দুটো একে অপরের উল্টো অপারেশন পরপর সাজানো:
```text
পর্যায় 1 (update): difference array — diff[l] += x; diff[r+1] -= x
পর্যায় 2 (build) : diff-এর prefix sum → চূড়ান্ত array a
পর্যায় 3 (query) : a-র prefix sum P → range sum = P[qr+1] - P[ql]
```
লক্ষ করো prefix sum দুবার এসেছে — একবার difference থেকে আসল array ফেরাতে, আরেকবার সেই array-র উপর fast query-র জন্য। মূল গণিত সেই দুই জোড়া বিপরীত অপারেশন: difference ↔ prefix (069), এবং range-sum ↔ prefix-difference (068)।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
দুটোই সরাসরি loop দিয়ে: update-এ range ধরে যোগ, query-তে range ধরে যোগ:
```python
def solve_brute(n, updates, queries):
a = [0] * n
for l, r, x in updates:
for i in range(l, r + 1): # update: range ধরে যোগ
a[i] += x
ans = []
for ql, qr in queries:
ans.append(sum(a[ql:qr + 1])) # query: range ধরে যোগ
return ans
```
সরল, ঠিক উত্তর দেয় — কিন্তু update আর query দুটোতেই range ধরে হাঁটছে।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
ধরো q_u টা update, প্রতিটা O(n) → update-এ O(n × q_u)। আর q_q টা query, প্রতিটা O(n) → query-তে O(n × q_q)। মোট **O(n × (q_u + q_q))**।
```text
n = 100000, q_u = q_q = 100000 হলে:
brute force: ~2 × 10^10 operation — TLE
pipeline : O(n + q_u) update-side + O(n + q_q) query-side ≈ 4×10^5 — দ্রুত
```
দুই জায়গাতেই একই অপচয়: overlapping range বারবার যোগ হচ্ছে। update-এ difference array সেটা কাটে, query-তে prefix sum কাটে।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight: দুই পর্যায়ে দুই কৌশল। update-গুলো difference array-তে O(1) করে জমাও, একবার prefix চালিয়ে final array পাও (069)। তারপর সেই final array-র উপর আরেকটা prefix বানিয়ে প্রতিটা query O(1) (068):
```python
def solve(n, updates, queries):
diff = [0] * (n + 1)
for l, r, x in updates:
diff[l] += x
diff[r + 1] -= x
a = [0] * n
run = 0
for i in range(n):
run += diff[i]
a[i] = run
P = [0] * (n + 1) # final array-র prefix (query-র জন্য)
for i in range(n):
P[i + 1] = P[i] + a[i]
return [P[qr + 1] - P[ql] for ql, qr in queries]
```
মোট **O(n + q_u + q_q)** — সবগুলো ধাপ linear। brute-এর গুণফল থেকে যোগফলে নেমে এল।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা!" মুহূর্ত: **update আর query আলাদা প্রকৃতির — তাদের আলাদা কৌশল দাও, আর ক্রমে সাজাও।** "সব বদল আগে, তারপর সব প্রশ্ন" — এই বিভাজনটাই সরল কৌশলটাকে সম্ভব করে।
দ্বিতীয় tweak: prefix sum এখানে দুই ভূমিকায় — একবার difference-কে undo করে আসল array ফেরায়, আরেকবার সেই array-কে query-ready বানায়। একই হাতিয়ার, দুই কাজ। (যদি update আর query মাঝপথে মিশত, তখন এই ক্রম ভেঙে পড়ত — তখন BIT/segment tree।)
### ছবিতে বোঝা {#5-visual-explanation}
`n = 5`। Updates: `(0, 2, 3)`, `(1, 4, 2)`। তারপর query `(1, 3)`।
```text
পর্যায় 1 — difference array (দুই প্রান্তে দাগ):
শুরু: diff = [0, 0, 0, 0, 0, 0]
(0, 2, +3): diff = [3, 0, 0, -3, 0, 0]
(1, 4, +2): diff = [3, 2, 0, -3, 0, -2]
পর্যায় 2 — prefix চালিয়ে final array:
running: 3 → 3+2=5 → 5+0=5 → 5-3=2 → 2+0=2
a = [ 3, 5, 5, 2, 2 ]
index 0 1 2 3 4
পর্যায় 3 — a-র prefix P, তারপর range query:
P = [0, 3, 8, 13, 15, 17]
sum(1..3) = P[4] - P[1] = 15 - 3 = 12 (5 + 5 + 2 = 12 ✓)
```
তিন পর্যায় তিন রঙে ভাবো: দাগ দেওয়া → আসল array ফেরানো → query-র জন্য আবার prefix। প্রতিটা পর্যায়ই আসলে prefix/difference-এর চেনা মুখ, শুধু পরপর সাজানো।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`n = 5`, updates `(0, 2, 3)`, `(1, 4, 2)`, query `(1, 3)`।
পর্যায় 1 — difference:
| update | diff পরিবর্তন | diff এখন |
| --- | --- | --- |
| (0, 2, 3) | diff[0]+=3, diff[3]-=3 | [3, 0, 0, -3, 0, 0] |
| (1, 4, 2) | diff[1]+=2, diff[5]-=2 | [3, 2, 0, -3, 0, -2] |
পর্যায় 2 — prefix → final array:
| i | diff[i] | run | a[i] |
| --- | --- | --- | --- |
| 0 | 3 | 3 | 3 |
| 1 | 2 | 5 | 5 |
| 2 | 0 | 5 | 5 |
| 3 | -3 | 2 | 2 |
| 4 | 0 | 2 | 2 |
পর্যায় 3 — final array-র prefix `P = [0, 3, 8, 13, 15, 17]`। query `(1, 3)`: `P[4] - P[1] = 15 - 3 = 12`। মিলিয়ে: 5+5+2 = 12 ✓।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def solve(n, updates, queries):
"""পর্যায় 1: difference array দিয়ে update; পর্যায় 2: prefix → final array;
পর্যায় 3: final array-র prefix দিয়ে প্রতি query O(1)। সব O(n + q)।"""
diff = [0] * (n + 1)
for l, r, x in updates:
diff[l] += x
diff[r + 1] -= x
a = [0] * n # final array (update-পরবর্তী)
run = 0
for i in range(n):
run += diff[i]
a[i] = run
P = [0] * (n + 1) # final array-র prefix (query-র জন্য)
for i in range(n):
P[i + 1] = P[i] + a[i]
return [P[qr + 1] - P[ql] for ql, qr in queries]
def solve_brute(n, updates, queries):
"""ধীর version — মিলিয়ে দেখার জন্য।"""
a = [0] * n
for l, r, x in updates:
for i in range(l, r + 1):
a[i] += x
return [sum(a[ql:qr + 1]) for ql, qr in queries]
# --- ছোট test গুলো (সব pass করা উচিত) ---
n = 5
updates = [(0, 2, 3), (1, 4, 2)]
queries = [(1, 3), (0, 4), (2, 2), (0, 0)]
assert solve(n, updates, queries) == [12, 17, 5, 3]
assert solve(3, [], [(0, 2), (1, 1)]) == [0, 0] # update নেই
assert solve(3, [(2, 2, 7)], [(0, 2), (2, 2)]) == [7, 7] # শেষ index update
# fast আর brute একই উত্তর দেয় কিনা (random brute-force cross-check):
import random
random.seed(7)
def rand_range(m):
"""0..m-1 থেকে এলোমেলো (l, r) জোড়া, l <= r।"""
l = random.randint(0, m - 1)
r = random.randint(0, m - 1)
return (min(l, r), max(l, r))
for _ in range(300):
m = random.randint(1, 8)
ups = []
for _ in range(random.randint(0, 5)):
l, r = rand_range(m)
ups.append((l, r, random.randint(-5, 5)))
qs = [rand_range(m) for _ in range(random.randint(1, 5))]
assert solve(m, ups, qs) == solve_brute(m, ups, qs)
print(solve(n, updates, queries)) # [12, 17, 5, 3]
print(solve(3, [(2, 2, 7)], [(0, 2)])) # [7]
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
diff = [0] * (n + 1)
for l, r, x in updates:
diff[l] += x
diff[r + 1] -= x
```
পর্যায় 1 — 069-এর difference array। প্রতিটা update দুটো দাগে, O(1)।
```text
run = 0
for i in range(n):
run += diff[i]
a[i] = run
```
পর্যায় 2 — diff-এর উপর prefix sum চালিয়ে update-পরবর্তী আসল array `a`।
```text
P = [0] * (n + 1)
for i in range(n):
P[i + 1] = P[i] + a[i]
```
পর্যায় 3-এর প্রস্তুতি — final array `a`-র prefix `P` (067)। এবার যেকোনো range sum এক বিয়োগে।
```text
return [P[qr + 1] - P[ql] for ql, qr in queries]
```
প্রতিটা query: `P[qr+1] - P[ql]` (068)। সব O(1)।
বাকি `assert` গুলো নির্দিষ্ট উদাহরণ + random brute-force cross-check দিয়ে fast আর brute মিলিয়ে দেখছে। সব মিললে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
`solve(5, [(0,2,3),(1,4,2)], [(1,3),(0,4),(2,2),(0,0)])`:
- update → `diff = [3, 2, 0, -3, 0, -2]`
- prefix → `a = [3, 5, 5, 2, 2]`
- final prefix → `P = [0, 3, 8, 13, 15, 17]`
- queries → `[12, 17, 5, 3]` → প্রথম `print`
- `solve(3, [(2,2,7)], [(0,2)])` → `a = [0,0,7]`, query → `[7]` → দ্বিতীয় `print`
- সব `assert` pass → `সব test pass!`
ছাপা output:
```text
[12, 17, 5, 3]
[7]
সব test pass!
```
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(n + q_u + q_q)** — update O(q_u) + দুটো prefix pass O(n) + query O(q_q)। সবগুলো ধাপ linear, কোনো nested loop নেই। brute-এর O(n × (q_u + q_q)) থেকে গুণফল-কে-যোগফলে নামার সেই চেনা লাফ।
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(n)** — `diff`, `a`, `P` তিনটাই O(n) array। চাইলে `a`-কেই reuse করে একটা কমানো যায়, কিন্তু আলাদা রাখা পরিষ্কার।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **পর্যায়ের ক্রম গুলিয়ে ফেলা** — সব update আগে শেষ করো, *তারপর* prefix, *তারপর* query। মাঝপথে query করলে diff তখনো final array না।
2. **update-এর off-by-one আর query-র off-by-one মেলানো** — update-এ `diff[r+1] -= x`, query-তে `P[qr+1] - P[ql]`; দুটো আলাদা, গুলিয়ো না।
3. **final array-র prefix না বানিয়ে সরাসরি `a`-তে query loop** — তাহলে query আবার O(n), pipeline-এর লাভ হারালে।
4. **`diff` n ঘর বানানো** — `r` শেষ index হলে `diff[r+1]` out-of-range; n+1 রাখো।
5. **update আর query মাঝপথে মেশা ধরে নেওয়া** — এই সরল কৌশল তখন চলে না; প্রশ্নে "আগে সব update" না থাকলে BIT/segment tree ভাবো।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **CSES — Range Update Queries** (