Concept Notes — Prefix, Difference, Contribution (ভেতর থেকে বোঝা)¶
এই level-এর তিনটা কৌশলের পেছনে একটাই প্রশ্ন: "একই হিসাব বারবার করছি না তো?" যেখানেই উত্তর হ্যাঁ, সেখানেই precompute করার সুযোগ। চলো একটা একটা করে ছবি বানাই।
1. Prefix sum = দোকানদারের running total¶
ধরো array a = [2, 5, 1, 3, 4]। কেউ জিজ্ঞেস করল "index 1 থেকে 3 পর্যন্ত sum কত?" — loop চালালে O(n)। কিন্তু এমন প্রশ্ন যদি 10^5 বার আসে? প্রতিবার loop = মোট O(n × q) — মরে গেলাম।
সমাধান: আগে থেকেই শুরু থেকে প্রতিটা জায়গা পর্যন্ত মোট লিখে রাখো। এটাই prefix sum:
a = [2, 5, 1, 3, 4]
P = [0] * (len(a) + 1) # P[0] = 0 — sentinel, এটাই জাদুর চাবি
for i in range(len(a)):
P[i + 1] = P[i] + a[i]
# P = [0, 2, 7, 8, 11, 15]
Mini dry run:
i = 0: P[1] = 0 + 2 = 2
i = 1: P[2] = 2 + 5 = 7
i = 2: P[3] = 7 + 1 = 8
i = 3: P[4] = 8 + 3 = 11
i = 4: P[5] = 11 + 4 = 15
P[i] মানে: "প্রথম i টা element-এর মোট"। এবার রেঞ্জের sum বের করা হলো ফিতা কাটার মতো — পুরো ফিতা থেকে বাঁ দিকের অপ্রয়োজনীয় টুকরো কেটে ফেলো:
┌── P[4] = 11 (প্রথম 4টার মোট) ──┐
a: [2] [5] [1] [3] [4]
└P[1]┘└── এটুকুই চাই ──┘
sum(1..3) = P[4] - P[1] = 11 - 2 = 9 (5 + 1 + 3 ✓)
সাধারণ নিয়ম (0-indexed, P-র দৈর্ঘ্য n+1): sum(l..r) = P[r + 1] - P[l]। বানাতে O(n), প্রতি query O(1)। দোকানদার দিনশেষে খাতা একবারই যোগ করে — তারপর যে-ই জিজ্ঞেস করুক, উত্তর তৈরি।
2. Difference array = prefix-এর আয়নার উল্টো পিঠ¶
Prefix-এ ছিল: array দেওয়া, range-এর প্রশ্ন অনেক। এবার উল্টো: range-এ update অনেক ("l থেকে r পর্যন্ত সবার সাথে x যোগ করো"), শেষে পুরো array চাই।
প্রতিবার loop চালালে আবার O(n × q)। চালাকি: পুরো রেঞ্জে লেখার বদলে শুধু দুই প্রান্তে দাগ দাও — "এখান থেকে +x শুরু" আর "এখানে এসে +x শেষ":
n = 5
diff = [0] * (n + 1) # এক ঘর বেশি — r+1 এর জায়গা
def range_add(l, r, x):
diff[l] += x # এখান থেকে x-এর প্রভাব শুরু
diff[r + 1] -= x # এখানে এসে প্রভাব শেষ
range_add(1, 3, 10)
range_add(2, 4, 5)
a = [0] * n
running = 0
for i in range(n):
running += diff[i] # দাগগুলোর উপর দিয়ে হাঁটা = prefix sum!
a[i] = running
print(a) # [0, 10, 15, 15, 5]
Mini dry run:
update 1: diff = [0, +10, 0, 0, -10, 0]
update 2: diff = [0, +10, +5, 0, -10, -5]
হাঁটা: running = 0 → 0+10=10 → 10+5=15 → 15 → 15-10=5 → (শেষ)
a = [0, 10, 15, 15, 5] ✓
ছবিটা ভাবো: রাস্তায় দুটো সাইনবোর্ড — "টোল শুরু" আর "টোল শেষ"। মাঝের প্রতিটা গাড়ি টোল দেয়, কিন্তু সাইনবোর্ড মাত্র দুটো। q টা update = O(q), শেষে এক pass prefix = O(n)। Difference নেয় update, prefix বানায় উত্তর — দুটো অপারেশন একে অপরের উল্টো, ঠিক যেমন derivative আর integral।
3. Prefix XOR — template এক, operator বদল¶
Level 4 মনে আছে? XOR self-inverse: a ^ a = 0। তাহলে যোগের জায়গায় XOR বসালেও prefix কৌশল চলে — কারণ "বাঁ দিকের টুকরো বাদ দেওয়া"-র কাজটা বিয়োগের বদলে আবার XOR-ই করে:
a = [3, 5, 2, 7]
PX = [0] * (len(a) + 1)
for i in range(len(a)):
PX[i + 1] = PX[i] ^ a[i]
# PX = [0, 3, 6, 4, 3]
# xor(l..r) = PX[r+1] ^ PX[l]
print(PX[3] ^ PX[1]) # xor(1..2) = 5 ^ 2 = 7 ✓
কেন কাজ করে: PX[3] = 3 ^ 5 ^ 2, আর PX[1] = 3। দুটো XOR করলে 3 দুবার এসে কেটে যায় — পড়ে থাকে 5 ^ 2। বিয়োগ যা subtraction-এ করে, XOR তা cancel-এ করে। এই দেখার চোখটা মূল্যবান: prefix কৌশল চলে যেকোনো operation-এ যার "undo" আছে (যোগ ↔ বিয়োগ, XOR ↔ XOR)। Min/max-এর undo নেই — তাই prefix min দিয়ে যেকোনো range-এর min হয় না।
4. 2D prefix sum — rectangle আর inclusion-exclusion¶
Matrix-এ "এই rectangle-এর sum কত?" — একই গল্প, এবার দুই দিকে। P[i][j] = উপরের-বাঁ কোণ থেকে (i-1, j-1) পর্যন্ত rectangle-এর মোট। Query-র ছবি:
┌───────────┬─────┐
│ B │ . │ চাই: ভেতরের ছোট rectangle (★)
├─────┬─────┤ │
│ C │ ★ │ │ পুরো বড়টা (P[r2][c2]) থেকে
├─────┴─────┘ │ উপরের পট্টি (B সহ) বাদ,
│ A │ বাঁয়ের পট্টি (C সহ) বাদ —
└─────────────────┘ কিন্তু কোণার ব্লক দুবার কাটা পড়ল, একবার ফেরত!
# P-র size (rows+1) x (cols+1), সব sentinel 0
# build: P[i+1][j+1] = mat[i][j] + P[i][j+1] + P[i+1][j] - P[i][j]
# query sum of rect (r1,c1)..(r2,c2):
ans = P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]
4-টা term মুখস্থ নয় — উপরের ছবিটা আঁকো: বড় থেকে দুই পট্টি বাদ, কোণা ফেরত। এটাই inclusion-exclusion, Level 3-এর সেই Venn-চিন্তারই geometry version।
5. Subarray Sum = K — "P[r] - K কি আগে দেখেছি?"¶
এবার তারকা problem। "কয়টা subarray-র sum ঠিক K?" — সব (l, r) try করলে O(n²)। চাবি হলো এই সমীকরণটা উল্টে পড়া:
sum(l..r) = K
P[r] - P[l-1] = K
P[l-1] = P[r] - K ← r-এ দাঁড়িয়ে প্রশ্ন: "P[r] - K মানের prefix কি আগে কোথাও হয়েছিল?"
প্রতিটা r-এ পেছনের সব l খোঁজার দরকার নেই — শুধু জানতে হবে মান P[r] - K কতবার আগে এসেছে। গোনার জন্য hash map। চিনতে পারছ? এটা Two Sum-এর হুবহু চাল — "complement আগে দেখেছি কি?" (hash-এর গভীরে: ../../05-hashing/)।
def subarray_sum_k(a, K):
from collections import defaultdict
seen = defaultdict(int)
seen[0] = 1 # খালি prefix — index 0 থেকে শুরু subarray-র জন্য
P, count = 0, 0
for x in a:
P += x
count += seen[P - K] # আগে কতবার P-K দেখেছি = তত নতুন subarray
seen[P] += 1 # নিজেরটা এখন লিখে রাখলাম
return count
print(subarray_sum_k([1, 2, 3], 3)) # 2 → [1,2] আর [3]
Mini dry run (a = [1, 2, 3], K = 3):
শুরুতে seen = {0: 1}
x=1: P=1, খুঁজি 1-3=-2 → নেই (0)। seen = {0:1, 1:1}
x=2: P=3, খুঁজি 3-3=0 → আছে 1 বার! count=1। seen = {0:1, 1:1, 3:1}
x=3: P=6, খুঁজি 6-3=3 → আছে 1 বার! count=2। seen = {..., 6:1}
উত্তর: 2 ✓
seen[0] = 1 লাইনটা ভুললে [1, 2] (যেটা একদম শুরু থেকে) ধরা পড়ত না — এটাই এই problem-এর কুখ্যাত bug।
6. Divisible by K — remainder-এর জোড়া¶
"কয়টা subarray-র sum K দিয়ে ভাগ যায়?" — সমীকরণ এবার mod-এ:
মানে: একই remainder-ওয়ালা দুটো prefix = একটা valid subarray। তাহলে remainder ধরে ধরে গোনো — প্রতি r-এ "আমার remainder আগে কতবার এসেছে" যোগ করো। Code টা section 5-এর প্রায় copy — শুধু P - K খোঁজার বদলে P % K খোঁজা, আর seen[0] = 1 একই কারণে থাকে। (Level 2-এর mod-চিন্তা এখানে ফসল দিল!)
7. Contribution — প্রশ্নটা উল্টে দাও¶
"সব subarray-র sum-এর যোগফল কত?" — n² টা subarray, প্রতিটার sum বের করা মানে কান্না। দৃষ্টিভঙ্গি উল্টাও: subarray ধরে না গুনে প্রতিটা element-কে জিজ্ঞেস করো — "তুমি মোট কয়টা subarray-তে আছ?" যে যতবার আছে, মোট sum-এ সে ততবার নিজের মান জমা দেয়।
a[i] কয়টা subarray-তে? Subarray-টার শুরু হতে হবে i-এর বাঁয়ে বা i-তে — option i + 1টা (index 0..i)। শেষ হতে হবে i-তে বা ডানে — option n - iটা (index i..n-1)। স্বাধীন পছন্দ, তাই গুণ:
a = [x, y, z], n = 3, ধরো i = 1 (y)
শুরু: 0 বা 1 → 2টা option (i + 1 = 2)
শেষ: 1 বা 2 → 2টা option (n - i = 2)
y আছে 2 × 2 = 4টা subarray-তে: [x,y] [x,y,z] [y] [y,z] ✓
def sum_of_all_subarrays(a):
n = len(a)
return sum(a[i] * (i + 1) * (n - i) for i in range(n))
print(sum_of_all_subarrays([1, 2, 3])) # 20
Dry run: 1×(1×3) + 2×(2×2) + 3×(3×1) = 3 + 8 + 9 = 20। হাতে মিলাও: subarray গুলো [1],[2],[3],[1,2],[2,3],[1,2,3] → sum গুলো 1+2+3+3+5+6 = 20 ✓। O(n²) নেমে এল O(n)-এ — শুধু প্রশ্নটা ঘুরিয়ে।
এটাই contribution technique: মোটের হিসাবকে ভেঙে দাও "প্রতিটা টুকরো মোটে কত যোগ করে"-তে। Pair নিয়ে problem-এও একই চাল — প্রতি pair-এর বদলে প্রতি element ভাবো "আমি কয়টা pair-এ কী ভূমিকায়?"
8. Sum of Subarray Minimums — contribution-এর কঠিন রূপ¶
"সব subarray-র minimum-এর যোগফল?" — এবার a[i]-র contribution = (যে subarray গুলোতে সে-ই minimum, সেগুলোর সংখ্যা) × a[i]। কয়টায় সে minimum? যতদূর বাঁয়ে গেলে তার চেয়ে ছোট কেউ নেই × যতদূর ডানে। অর্থাৎ দরকার প্রতিটা i-এর জন্য nearest smaller element বাঁয়ে আর ডানে — এই "span" খোঁজার দ্রুত যন্ত্রের নাম monotonic stack, যার আসল বাড়ি ../../04-stack-and-queue/।
a = [3, 1, 2, 4], i = 1 (মান 1)
বাঁয়ে 1-এর ছোট কেউ নেই → বাঁ span-এ 2টা শুরু-option (index 0, 1)
ডানে 1-এর ছোট কেউ নেই → ডান span-এ 3টা শেষ-option (index 1, 2, 3)
1 minimum থাকে 2 × 3 = 6টা subarray-তে → contribution = 1 × 6 = 6
এখানে শুধু কাঠামোটা নাও: contribution × span। বিস্তারিত problem 077-এর note-এ।
9. Imos method আর sweep line — event-এর জগতে difference¶
Imos method আসলে difference array-রই আরেক নাম, শুধু দৃষ্টিটা event-ভিত্তিক: "একজন অতিথি সময় l-এ ঢোকে, r-এ বেরোয়" মানে timeline-এ +1 দাগ l-এ, -1 দাগ r-এ (বা r+1-এ, প্রান্ত-নিয়ম অনুযায়ী)। সব অতিথির দাগ বসিয়ে এক pass prefix — প্রতি মুহূর্তে কতজন ভেতরে, বেরিয়ে গেল।
Sweep line সেটারই sorted-event রূপ — timeline টা array না হয়ে যখন বিশাল বা continuous, তখন শুধু event গুলো sort করে বাঁ থেকে ডানে "ঝাড়ু" চালাও:
def max_overlap(intervals):
events = []
for l, r in intervals:
events.append((l, +1)) # ঢুকল
events.append((r, -1)) # বেরোল
events.sort()
best = cur = 0
for _, delta in events:
cur += delta
best = max(best, cur)
return best
print(max_overlap([(1, 4), (2, 5), (3, 6)])) # 3
Mini dry run: sorted events = (1,+1) (2,+1) (3,+1) (4,-1) (5,-1) (6,-1) → cur যায় 1, 2, 3, 2, 1, 0 → best 3 ✓। একই বিন্দুতে ঢোকা-বেরোনো থাকলে কোনটা আগে — এই tie-এর নিয়মটা problem অনুযায়ী ঠিক করতে হয় (079/080-এর note-এ বিস্তারিত)।
এক নজরে cheat sheet¶
prefix build : P[i+1] = P[i] + a[i] (P[0] = 0 sentinel)
range sum : P[r+1] - P[l]
range update : diff[l] += x; diff[r+1] -= x; শেষে এক pass prefix
range XOR : PX[r+1] ^ PX[l]
2D query : P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]
sum == K গোনা : hash map, seen[0]=1, প্রতি ধাপে seen[P-K] যোগ
divisible by K : একই কাঠামো, key = P % K
contribution : a[i] আছে (i+1) * (n-i) subarray-তে
sweep line : (+1, -1) events sort → running count
প্রতিটা লাইনের পেছনে একটা ছবি আছে — ফিতা, সাইনবোর্ড, rectangle, জোড়া remainder, বাঁ-ডান পছন্দ। Formula ভুলে গেলে ছবিতে ফেরো — formula নিজেই ফিরে আসবে।