069 — Difference Array¶
এতক্ষণ array দেওয়া ছিল, range-এর প্রশ্ন অনেক ছিল (067-068)। এবার পুরো গল্প উল্টো: range-এ update অনেক ("l থেকে r পর্যন্ত সবার সাথে x যোগ করো"), শেষে চূড়ান্ত array চাই। চালাকিটা সুন্দর — পুরো রেঞ্জে না লিখে শুধু দুই প্রান্তে দাগ দাও। রাস্তায় "টোল শুরু / টোল শেষ" সাইনবোর্ডের ছবিটা মনে রাখো।
Source¶
- Original source: Classic technique (difference array)
- Platform: Classic technique (USACO Guide silver) — https://usaco.guide/silver/more-prefix-sums
- 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
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 বের করা যায়।
2. What is the math idea?¶
মূল idea হলো difference array — prefix sum-এর ঠিক উল্টো অপারেশন।
একটা সহায়ক array diff রাখি যেখানে diff[i] = a[i] - a[i-1] (পরপর দুই element-এর পার্থক্য)। এর জাদু:
মাত্র দুটো জায়গায় দাগ! আর শেষে diff-এর উপর একবার prefix sum চালালেই আসল array ফিরে আসে। কারণ prefix sum হলো difference-এর "undo" — ঠিক যেমন integral হলো derivative-এর উল্টো।
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 না বুঝলে এটা আটকে যাবে।
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 সামলালে।
5. Visual explanation¶
n = 5, শুরুতে সব 0। দুটো update: range_add(1, 3, 10) আর range_add(2, 4, 5)। diff-এর দৈর্ঘ্য n+1 = 6 (r+1-এর জায়গা):
শুরু: 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 সামলে গেল।
6. Example input and output¶
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] লেখার জায়গা থাকে।
7. Brute force thinking¶
প্রতিটা update-এ সরাসরি range ধরে loop চালিয়ে যোগ:
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)।
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:
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)-এও ফিরবে।
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 ফিরে এল ✓।
12. Python solution¶
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¶
difference array, n+1 ঘর। বাড়তি ঘরটা diff[r+1]-এর জন্য, যখন r শেষ index।
প্রতিটা update মাত্র দুটো লাইন: l-এ x ঢুকল ("শুরু"), r+1-এ x বেরোল ("শেষের পর")। range যত বড়ই হোক, এই দুটো দাগ — তাই O(1)।
এটাই prefix sum (067)। দাগগুলোর উপর দিয়ে হাঁটছি, running total রাখছি — সেটাই প্রতিটা index-এর আসল মান। "শুরু" দাগ পেরোলে running বাড়ে, "শেষ" দাগ পেরোলে কমে।
বাকি assert গুলো fast আর brute মিলিয়ে দেখছে (brute-force cross-check), edge case (r=শেষ, খালি update) সহ। সব মিললে সব test pass!।
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:
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¶
diff[r+1] -= xভুলে যাওয়া — তাহলে +x array-র শেষ পর্যন্ত গড়িয়ে যায়, update কখনো "শেষ" হয় না। দুই দাগই বাধ্যতামূলক।diff-কে n ঘর বানানো (n+1 না) —rযখন শেষ index,diff[r+1]out-of-range। সবসময় n+1 ঘর রাখো।r(r+1 না) তে বিয়োগ —diff[r] -= xদিলেa[r]নিজেও কমে যায়; প্রভাবr-এ থামার বদলে এক ঘর আগে থামে। বিয়োগr+1-এ।- মাঝপথে query করার চেষ্টা — এই সরল কৌশল কাজ করে শুধু "সব update আগে, তারপর একবার prefix" হলে। update আর query মিশে থাকলে BIT/segment tree লাগে।
- prefix চালাতে ভুলে diff-কেই answer ভাবা —
diffশুধু দাগ, আসল array নয়। শেষে prefix sum চালানো বাধ্যতামূলক।
18. Harder problems that inherit this idea¶
- LeetCode — Corporate Flight Bookings (https://leetcode.com/problems/corporate-flight-bookings/) — হুবহু difference array-র প্রয়োগ (range-এ seat যোগ)।
- LeetCode — Range Addition (https://leetcode.com/problems/range-addition/) — এই problem-এরই সরাসরি রূপ।
- 070 (Range Update Query) — এই repo-তে পরের ধাপ: update + শেষে query-র পূর্ণ pipeline।
19. Pattern learned¶
Range update via difference array — diff[l] += x; diff[r+1] -= x, শেষে এক pass prefix sum। বড় শিক্ষা: ব্যাপ্ত range-update কে দুটো প্রান্তিক event-এ নামিয়ে আনো; difference নেয় update, prefix বানায় answer — দুটো পরস্পরের উল্টো।
20. Final summary¶
ভবিষ্যতের আমাকে এক লাইনে: "range-এ +x = diff[l] += x; diff[r+1] -= x (diff এক ঘর বড়), শেষে একবার prefix sum চালাও। difference আর prefix আয়নার দুই পিঠ — অনেক update থাকলেই এই pattern।"
পরের ধাপ → 070 — Range Update Query (update + শেষে range query-র পূর্ণ pipeline)। সম্পর্কিত → 079 — Imos Method Basic (event-এর জগতে এই difference)।
ফিরে দেখা: শিকড় → 067 — Prefix Sum · এই level-এর map → ../README.md · concept ঝালাই → ../concept-notes.md · template → ../../../templates/math-problem-note-template.md।
মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখো; problem statement copy কোরো না; official link শুধু attribution-এর জন্য রাখো; "asked by Google/Amazon" এমন দাবি কোরো না — বরং "Google-style pattern" / "common interview pattern" লেখো।