070 — Range Update Query

069-এ দুটো দাগ দিয়ে range update শিখলে। এবার সেটা একটা পূর্ণ pipeline-এ বাঁধব: প্রথমে অনেকগুলো range update, তারপর difference থেকে prefix চালিয়ে final array, আর শেষে সেই final array-র উপর 067-068-এর range query। অর্থাৎ এই note-এ Level 5-এর প্রথম তিন idea একসাথে হাত মেলায়। ধীরে পড়ো — ক্রমটাই আসল।

Source

• Original source: Classic exercise (difference array + prefix query pipeline)
• Platform: Classic exercise — https://usaco.guide/silver/more-prefix-sums
• 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

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)।

2. What is the math idea?

দুটো একে অপরের উল্টো অপারেশন পরপর সাজানো:

পর্যায় 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)।

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-এ সব ঝালাই হয়ে যায়।

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-এর প্রাণ।

5. Visual explanation

n = 5। Updates: (0, 2, 3), (1, 4, 2)। তারপর query (1, 3)।

পর্যায় 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-এর চেনা মুখ, শুধু পরপর সাজানো।

6. Example input and output

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।

7. Brute force thinking

দুটোই সরাসরি loop দিয়ে: update-এ range ধরে যোগ, query-তে range ধরে যোগ:

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))।

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):

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।)

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 ✓।

12. Python solution

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

diff = [0] * (n + 1)
for l, r, x in updates:
    diff[l] += x
    diff[r + 1] -= x

পর্যায় 1 — 069-এর difference array। প্রতিটা update দুটো দাগে, O(1)।

run = 0
for i in range(n):
    run += diff[i]
    a[i] = run

পর্যায় 2 — diff-এর উপর prefix sum চালিয়ে update-পরবর্তী আসল array a।

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 এক বিয়োগে।

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!।

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:

[12, 17, 5, 3]
[7]
সব test pass!

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 ভাবো।

18. Harder problems that inherit this idea

• CSES — Range Update Queries (https://cses.fi/problemset/task/1651) — update + point query; difference/BIT-এর ধারণা গভীরে নেয়।
• LeetCode — Range Addition (https://leetcode.com/problems/range-addition/) — pipeline-এর update অংশ।
• 079 (Imos Method Basic) আর 080 (Sweep Line Intro) — এই repo-তে পরের ধাপ: difference-চিন্তা event-এর জগতে।

19. Pattern learned

Difference-array update + prefix-sum query pipeline — update O(1) দাগে জমাও, prefix-এ final array, আবার prefix-এ query। বড় শিক্ষা: update আর query আলাদা প্রকৃতির; "সব বদল আগে, সব প্রশ্ন পরে" সাজালে দুই কৌশল সুন্দর জোড়া লাগে।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "range update + পরে range query = difference array (update) → prefix (final array) → prefix (query)। সব O(n + q)। শর্ত: সব update আগে, তারপর query — নইলে BIT/segment tree।"

পরের ধাপ → 071 — Prefix XOR (যোগের জায়গায় XOR বসিয়ে একই template)।

ফিরে দেখা: শিকড় → 069 — Difference Array, 068 — Range Sum Query · এই 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" লেখো।