Problem link ও উৎস
- **Original source:** Classic technique (difference array)
- **Platform:** Classic technique (USACO Guide silver) —
- **Topic:** Math-based programming fundamentals → Level 5: Prefix, Difference, Contribution
- **Difficulty:** Medium
- **Pattern:** range update via two-point marking
- **Basic idea inherited from:** 067 — Prefix Sum
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা array `a` (শুরুতে সব 0 ধরা যাক, দৈর্ঘ্য n)। তোমাকে অনেকগুলো **range update** করতে হবে: প্রতিটা update হলো "index `l` থেকে `r` পর্যন্ত প্রতিটা element-এর সাথে `x` যোগ করো"।
সব update শেষ হওয়ার পর চূড়ান্ত array-টা চাই। মুশকিল: update অনেক, আর প্রতিটা range বড় হতে পারে। প্রতিবার `l` থেকে `r` পর্যন্ত loop চালালে ধীর। তাই দরকার একটা চাল যাতে প্রতিটা update **O(1)**-এ লেখা যায়, আর শেষে একবারেই পুরো array বের করা যায়।
### Input ও output {#6-example-input-and-output}
```text
n = 5, শুরুতে সব 0
updates: (1, 3, 10), (2, 4, 5)
result a = [0, 10, 15, 15, 5]
আরও উদাহরণ:
n = 4, updates: (0, 3, 1) -> [1, 1, 1, 1] (পুরো array-তে +1)
n = 4, updates: (0, 0, 5) -> [5, 0, 0, 0] (একটা index)
n = 4, updates: (1, 2, 3), (1, 2, -3) -> [0, 0, 0, 0] (যোগ-বিয়োগ কাটাকাটি)
n = 3, updates: (2, 2, 7) -> [0, 0, 7] (r = শেষ index; r+1 array-র বাইরে, তাই diff এক ঘর বড়)
```
শেষ উদাহরণটা গুরুত্বপূর্ণ: `r` যখন শেষ index, `r+1` array-র বাইরে যায় — সেজন্যই `diff`-কে এক ঘর বড় (n+1) রাখি, যাতে `diff[r+1]` লেখার জায়গা থাকে।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো একটা মহাসড়কে টোল আদায়। তুমি বলতে চাও "km 1 থেকে km 3 পর্যন্ত প্রতিটা গাড়ি 10 টাকা টোল দেবে"।
তুমি কি প্রতিটা km-এ আলাদা বোর্ড লাগাবে? না! তুমি km 1-এ একটা বোর্ড লাগাও **"+10 টোল শুরু"**, আর km 4-এ একটা বোর্ড **"-10 টোল শেষ"**। মাঝের প্রতিটা গাড়ি km 1-এর "শুরু" পেরিয়েছে কিন্তু এখনো "শেষ" পায়নি — তাই তারা 10 টাকা টোল-এর আওতায়।
পরে যখন তুমি km ধরে ধরে হাঁটবে আর বোর্ডের সংখ্যা যোগ করতে থাকবে (running total = prefix sum), প্রতিটা km-এ ঠিক কত টোল চালু আছে বেরিয়ে আসবে। দুটো সাইনবোর্ড দিয়ে পুরো একটা range সামলালে।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
**067 (Prefix Sum)** থেকে — কিন্তু আয়নায় উল্টো করে। 067-এ ছিল array → prefix (যোগ জমাও)। এখানে difference → prefix দিয়ে array ফেরত পাচ্ছি।
মূল সম্পর্কটা: **prefix আর difference পরস্পরের বিপরীত।** যদি `diff` হয় `a`-র difference, তাহলে `diff`-এর prefix sum আবার `a`। এই দ্বৈততা বুঝলে difference array-র পুরো খেলা পরিষ্কার। শেষ ধাপে আমরা ঠিক 067-এর prefix-build চালাই — তাই 067 না বুঝলে এটা আটকে যাবে।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea হলো **difference array** — prefix sum-এর ঠিক উল্টো অপারেশন।
একটা সহায়ক array `diff` রাখি যেখানে `diff[i] = a[i] - a[i-1]` (পরপর দুই element-এর পার্থক্য)। এর জাদু:
```text
range-এ [l, r]-এ x যোগ মানে → diff[l] += x; diff[r+1] -= x
```
মাত্র দুটো জায়গায় দাগ! আর শেষে `diff`-এর উপর একবার **prefix sum** চালালেই আসল array ফিরে আসে। কারণ prefix sum হলো difference-এর "undo" — ঠিক যেমন integral হলো derivative-এর উল্টো।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
প্রতিটা update-এ সরাসরি range ধরে loop চালিয়ে যোগ:
```python
def apply_updates_brute(n, updates):
a = [0] * n
for l, r, x in updates:
for i in range(l, r + 1): # পুরো range-এ এক এক করে যোগ
a[i] += x
return a
```
সহজ, সরাসরি, ঠিক উত্তর দেয় — প্রতিটা update-এ ভেতরের loop পুরো range ঘুরে x যোগ করে।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
একটা update-এ ভেতরের loop চলে `(r - l + 1)` বার — খারাপ ক্ষেত্রে পুরো array, O(n)। q টা update হলে মোট **O(n × q)**।
```text
n = 100000, q = 100000 হলে:
brute force: ~10,000,000,000 operation (O(n·q)) — TLE
diff way : q × O(1) (দুটো দাগ) + O(n) (এক pass prefix) ≈ 300,000 — দ্রুত
```
অপচয়টা স্পষ্ট: একই index-এ অনেকগুলো overlapping update বারবার লিখছে। অথচ আসল দরকার শুধু "কোথায় প্রভাব শুরু, কোথায় শেষ" — মাঝের প্রতিটা ঘরে আলাদা করে লেখার দরকার নেই।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight: পুরো range-এ না লিখে শুধু **দুই প্রান্তে দাগ** দাও — `diff[l] += x` (শুরু), `diff[r+1] -= x` (শেষ)। প্রতিটা update O(1)। সব update শেষে একবার prefix sum চালিয়ে আসল array:
```python
def apply_updates(n, updates):
diff = [0] * (n + 1) # এক ঘর বড় — r+1 এর জায়গা
for l, r, x in updates:
diff[l] += x
diff[r + 1] -= x
a = [0] * n
running = 0
for i in range(n):
running += diff[i] # prefix sum = দাগের উপর হাঁটা
a[i] = running
return a
```
q টা O(1) update + একটা O(n) prefix pass = **O(n + q)**। brute-এর n×q থেকে বিশাল লাফ।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা!" মুহূর্ত: **একটা range-এ +x মানে কোনো ব্যাপ্ত কাজ নয় — মাত্র দুটো বিন্দু-ঘটনা: শুরুতে +x, শেষের পরে −x।** ব্যাপ্ত প্রভাবকে দুটো প্রান্তিক event-এ নামিয়ে আনা।
আর দ্বিতীয় tweak: সেই দুই দাগ থেকে আসল মান ফিরে পাওয়ার যন্ত্রটা হলো prefix sum (067)। মানে difference নেয় update, prefix বানায় answer — দুটো একে অপরের উল্টো। এই দ্বৈততা পরে imos method (079) আর sweep line (080)-এও ফিরবে।
### ছবিতে বোঝা {#5-visual-explanation}
`n = 5`, শুরুতে সব 0। দুটো update: range_add(1, 3, 10) আর range_add(2, 4, 5)। `diff`-এর দৈর্ঘ্য n+1 = 6 (r+1-এর জায়গা):
```text
শুরু: diff = [ 0, 0, 0, 0, 0, 0 ]
index 0 1 2 3 4 5
update (1, 3, +10): diff[1] += 10, diff[4] -= 10
diff = [ 0, +10, 0, 0, -10, 0 ]
update (2, 4, +5): diff[2] += 5, diff[5] -= 5
diff = [ 0, +10, +5, 0, -10, -5 ]
এবার prefix sum চালিয়ে (running total দিয়ে হাঁটা) আসল array:
index: 0 1 2 3 4
running: 0 → 0+10 → 10+5 → 15+0 → 15-10 = 5
0 10 15 15 5
a = [ 0, 10, 15, 15, 5 ]
```
ছবিটা ধরো: `+10` দাগ index 1-এ ঢুকল আর index 4-এ বেরোল — মাঝের 1,2,3 সবাই +10 পেল। `+5` দাগ 2-এ ঢুকে 5-এ বেরোল — 2,3,4 সবাই +5 পেল। দুটো overlap করল 2,3-এ, তাই সেখানে 15। দুটো দাগেই পুরো range সামলে গেল।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`n = 5`, updates: `(1, 3, 10)`, `(2, 4, 5)`। `diff = [0, 0, 0, 0, 0, 0]` (দৈর্ঘ্য 6) দিয়ে শুরু।
Update প্রয়োগ:
| update | diff[l] += x | diff[r+1] -= x | diff এখন |
| --- | --- | --- | --- |
| (1, 3, 10) | diff[1] += 10 | diff[4] -= 10 | [0, 10, 0, 0, -10, 0] |
| (2, 4, 5) | diff[2] += 5 | diff[5] -= 5 | [0, 10, 5, 0, -10, -5] |
এবার prefix sum (running total দিয়ে হাঁটা):
| i | diff[i] | running += diff[i] | a[i] |
| --- | --- | --- | --- |
| 0 | 0 | 0 | 0 |
| 1 | 10 | 10 | 10 |
| 2 | 5 | 15 | 15 |
| 3 | 0 | 15 | 15 |
| 4 | -10 | 5 | 5 |
শেষ অবস্থা: `a = [0, 10, 15, 15, 5]`। দুটো দাগ থেকে পুরো array ফিরে এল ✓।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def apply_updates(n, updates):
"""n দৈর্ঘ্যের 0-array-তে সব range update প্রয়োগ করে চূড়ান্ত array দেয়।
updates = [(l, r, x), ...]; range [l, r]-এ x যোগ। O(n + q)।"""
diff = [0] * (n + 1) # এক ঘর বড় (r+1 এর জন্য)
for l, r, x in updates:
diff[l] += x
diff[r + 1] -= x
a = [0] * n
running = 0
for i in range(n):
running += diff[i] # prefix sum = আসল মান ফিরিয়ে আনে
a[i] = running
return a
def apply_updates_brute(n, updates):
"""ধীর O(n·q) version — মিলিয়ে দেখার জন্য।"""
a = [0] * n
for l, r, x in updates:
for i in range(l, r + 1):
a[i] += x
return a
# --- ছোট test গুলো (সব pass করা উচিত) ---
assert apply_updates(5, [(1, 3, 10), (2, 4, 5)]) == [0, 10, 15, 15, 5]
assert apply_updates(4, [(0, 3, 1)]) == [1, 1, 1, 1]
assert apply_updates(4, [(0, 0, 5)]) == [5, 0, 0, 0]
assert apply_updates(4, [(1, 2, 3), (1, 2, -3)]) == [0, 0, 0, 0]
assert apply_updates(3, [(2, 2, 7)]) == [0, 0, 7] # r = শেষ index
assert apply_updates(3, []) == [0, 0, 0] # কোনো update নেই
# fast আর brute একই উত্তর দেয় কিনা (brute-force cross-check):
test_cases = [
(5, [(1, 3, 10), (2, 4, 5)]),
(6, [(0, 5, 2), (2, 2, 100), (1, 4, -1)]),
(4, [(0, 0, 5), (3, 3, -2), (0, 3, 1)]),
(1, [(0, 0, 9)]),
]
for n, ups in test_cases:
assert apply_updates(n, ups) == apply_updates_brute(n, ups)
print(apply_updates(5, [(1, 3, 10), (2, 4, 5)])) # [0, 10, 15, 15, 5]
print(apply_updates(4, [(0, 3, 1)])) # [1, 1, 1, 1]
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
diff = [0] * (n + 1)
```
difference array, n+1 ঘর। বাড়তি ঘরটা `diff[r+1]`-এর জন্য, যখন `r` শেষ index।
```text
for l, r, x in updates:
diff[l] += x
diff[r + 1] -= x
```
প্রতিটা update মাত্র দুটো লাইন: `l`-এ x ঢুকল ("শুরু"), `r+1`-এ x বেরোল ("শেষের পর")। range যত বড়ই হোক, এই দুটো দাগ — তাই O(1)।
```text
running = 0
for i in range(n):
running += diff[i]
a[i] = running
```
এটাই prefix sum (067)। দাগগুলোর উপর দিয়ে হাঁটছি, running total রাখছি — সেটাই প্রতিটা index-এর আসল মান। "শুরু" দাগ পেরোলে running বাড়ে, "শেষ" দাগ পেরোলে কমে।
বাকি `assert` গুলো fast আর brute মিলিয়ে দেখছে (brute-force cross-check), edge case (r=শেষ, খালি update) সহ। সব মিললে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
`apply_updates(5, [(1, 3, 10), (2, 4, 5)])`:
- দাগ বসানো: `diff = [0, 10, 5, 0, -10, -5]`
- prefix হাঁটা: running যায় `0, 10, 15, 15, 5` → `a = [0, 10, 15, 15, 5]` → প্রথম `print`
- `apply_updates(4, [(0, 3, 1)])` → পুরো array-তে +1 → `[1, 1, 1, 1]` → দ্বিতীয় `print`
- সব `assert` চুপচাপ pass
- শেষে `সব test pass!`
ছাপা output:
```text
[0, 10, 15, 15, 5]
[1, 1, 1, 1]
সব test pass!
```
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(n + q)** — q টা update প্রতিটা O(1) (দুটো দাগ), তারপর একটা O(n) prefix pass। brute-এর O(n × q)-এর তুলনায় বিশাল উন্নতি, বিশেষত অনেক বড় range-এর update-এ।
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(n)** — difference array `diff` (n+1) আর result array `a` (n)। দুটোই O(n)। update গুলো process করতে আর বাড়তি জায়গা লাগে না।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **`diff[r+1] -= x` ভুলে যাওয়া** — তাহলে +x array-র শেষ পর্যন্ত গড়িয়ে যায়, update কখনো "শেষ" হয় না। দুই দাগই বাধ্যতামূলক।
2. **`diff`-কে n ঘর বানানো (n+1 না)** — `r` যখন শেষ index, `diff[r+1]` out-of-range। সবসময় n+1 ঘর রাখো।
3. **`r` (r+1 না) তে বিয়োগ** — `diff[r] -= x` দিলে `a[r]` নিজেও কমে যায়; প্রভাব `r`-এ থামার বদলে এক ঘর আগে থামে। বিয়োগ `r+1`-এ।
4. **মাঝপথে query করার চেষ্টা** — এই সরল কৌশল কাজ করে শুধু "সব update আগে, তারপর একবার prefix" হলে। update আর query মিশে থাকলে BIT/segment tree লাগে।
5. **prefix চালাতে ভুলে diff-কেই answer ভাবা** — `diff` শুধু দাগ, আসল array নয়। শেষে prefix sum চালানো বাধ্যতামূলক।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **LeetCode — Corporate Flight Bookings** (