Concept Notes — Prefix, Difference, Contribution (ভেতর থেকে বোঝা)

সহজ করে শুরু: একই হিসাব বারবার করা এড়ানো

prefix[i]-তে প্রথম iটি উপাদানের যোগ রাখো; prefix[0]=0। তখন [l,r) অংশের যোগ prefix[r]-prefix[l]। Difference array বিপরীত দিকে কাজ করে: অনেক range update জমা রেখে শেষে একবার prefix নিয়ে ফল বানায়।

প্রোগ্রামে কোথায় ব্যবহার করবে: দিনভিত্তিক বিক্রির নির্দিষ্ট সময়ের যোগ, image-এর আয়তক্ষেত্রের মোট মান, অনেক range update এবং সব subarray-তে একটি উপাদানের মোট অবদান বের করতে লাগে।

কৌশল বাছার আগে শর্ত: এখানে range লেখার সময় [l,r) মানে l আছে, r নেই। সাধারণ prefix sum মূল array বদলে গেলে নিজে আপডেট হয় না; বারবার update ও query মিশলে Fenwick/segment tree দেখবে।

পড়ার ক্রম: এই পরিচয় → নিচের বিস্তারিত ধারণা → চিত্রে হাতে-কলমে হিসাব → সমস্যার তালিকা। প্রতিটি উদাহরণে আগে input, পরে বদলানো state, শেষে output মেলাও।

এই level-এর তিনটা কৌশলের পেছনে একটাই প্রশ্ন: "একই হিসাব বারবার করছি না তো?" যেখানেই উত্তর হ্যাঁ, সেখানেই precompute করার সুযোগ। চলো একটা একটা করে ছবি বানাই।

1. Prefix sum = দোকানদারের running total

ধরো array a = [2, 5, 1, 3, 4]। কেউ জিজ্ঞেস করল "index 1 থেকে 3 পর্যন্ত sum কত?" Loop চালালে O(n)। এমন qটি প্রশ্নে একইভাবে হিসাব করলে মোট O(n × q) সময় লাগবে।

সমাধান: আগে থেকেই শুরু থেকে প্রতিটা জায়গা পর্যন্ত মোট লিখে রাখো। এটাই prefix sum:

Python

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	আগের মোট P[i]	নতুন a[i]	নতুন মোট P[i+1]
0	0	2	2
1	2	5	7
2	7	1	8
3	8	3	11
4	11	4	15

P[i] মানে: "প্রথম i টা element-এর মোট"। এবার রেঞ্জের sum বের করা হলো ফিতা কাটার মতো — পুরো ফিতা থেকে বাঁ দিকের অপ্রয়োজনীয় টুকরো কেটে ফেলো:

প্রথম চারটির যোগ থেকে প্রথমটির যোগ বাদ

1. Array: index 1 থেকে 3 পর্যন্ত চাই

   02

   চিহ্নিত ঘর: 15↑ L

   চিহ্নিত ঘর: 21

   চিহ্নিত ঘর: 33↑ R

   44

   নির্বাচিত মান 5 + 1 + 3 = 9।

2. Prefix: সীমা দুটির মোট

   00

   চিহ্নিত ঘর: 12↑ L

   27

   38

   চিহ্নিত ঘর: 411↑ R+1

   515

   P[4] − P[1] = 11 − 2 = 9। ডানের সীমার জন্য R+1 নিই।

সাধারণ নিয়ম (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 শেষ":

Python

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-এর চারটি সীমানা, শেষে একটি prefix pass

1. ১. Index 1 থেকে 3-এ +10

   00

   চিহ্নিত ঘর: 110

   20

   30

   চিহ্নিত ঘর: 4-10

   50

   Index 1-এ চালু, index 4-এ বন্ধ। Index 5 হলো অতিরিক্ত sentinel।

2. ২. Index 2 থেকে 4-এ +5

   00

   110

   চিহ্নিত ঘর: 25

   30

   4-10

   চিহ্নিত ঘর: 5-5

   আগের দাগ রেখে নতুন শুরু ও শেষের দাগ যোগ করি।

3. ৩. বাঁ থেকে চলমান যোগ = চূড়ান্ত array

   00

   110

   চিহ্নিত ঘর: 215

   চিহ্নিত ঘর: 315

   45

   দুটি update একসঙ্গে কাজ করেছে index 2 ও 3-এ: 10 + 5 = 15।

ছবিটা ভাবো: রাস্তায় দুটো সাইনবোর্ড — "টোল শুরু" আর "টোল শেষ"। মাঝের প্রতিটা গাড়ি টোল দেয়, কিন্তু সাইনবোর্ড মাত্র দুটো। 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-ই করে:

Python

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-র ছবি:

নিচের ডানের 2×2 অংশের যোগ চাই

1. সারি 1–2, কলাম 1–2; সূচক শূন্য থেকে

   ফাঁকা বা বাদ দেওয়া ঘর: 1

   ফাঁকা বা বাদ দেওয়া ঘর: 2

   ফাঁকা বা বাদ দেওয়া ঘর: 3

   ফাঁকা বা বাদ দেওয়া ঘর: 4

   চিহ্নিত ঘর: 5

   চিহ্নিত ঘর: 6

   ফাঁকা বা বাদ দেওয়া ঘর: 7

   চিহ্নিত ঘর: 8

   চিহ্নিত ঘর: 9

   চাই 5 + 6 + 8 + 9 = 28। ওপরের row ও বাঁয়ের column বাদ দেব।

কাজ	যে অংশের যোগ	মান
পুরোটা নিই	1 থেকে 9-এর সব ঘর	+45
ওপরের row বাদ	1, 2, 3	−6
বাঁয়ের column বাদ	1, 4, 7	−12
দুবার বাদ পড়া কোণা ফেরত	1	+1
উত্তর	45 − 6 − 12 + 1	28

Python

# 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²)। চাবি হলো এই সমীকরণটা উল্টে পড়া:

যা চাই	একই কথা prefix দিয়ে
Half-open range [l,r)-এর যোগ K	P[r] - P[l] = K
বর্তমান prefix P[r] জানা আছে	আগের prefix চাই P[l] = P[r] - K

প্রতিটা r-এ পেছনের সব l খোঁজার দরকার নেই — শুধু জানতে হবে মান P[r] - K কতবার আগে এসেছে। গোনার জন্য hash map। চিনতে পারছ? এটা Two Sum-এর হুবহু চাল — "complement আগে দেখেছি কি?" (hash-এর গভীরে: ../../05-hashing/)।

Python

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}। টেবিলে শুধু positive frequency-র entries দেখানো হয়েছে; lookup-এর সময় defaultdict শূন্যের entry-ও তৈরি করতে পারে।

x	P	খুঁজি P−3	আগে পাওয়া বার	মোট count	ধাপ শেষে positive frequency
1	1	−2	0	0	{0:1, 1:1}
2	3	0	1	1	{0:1, 1:1, 3:1}
3	6	3	1	2	{0:1, 1:1, 3:1, 6:1}

উত্তর 2: [1,2] ও [3]।

seen[0] = 1 লাইনটা ভুললে [1, 2] (যেটা একদম শুরু থেকে) ধরা পড়ত না — এটাই এই problem-এর কুখ্যাত bug।

6. Divisible by K — remainder-এর জোড়া

"কয়টা subarray-র sum K দিয়ে ভাগ যায়?" — সমীকরণ এবার mod-এ:

Half-open [l,r) range-এ শর্ত (P[r] - P[l]) % K == 0। অর্থাৎ P[r] % K == P[l] % K।

মানে: একই 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-এর যোগফল কত?" Subarray-এর সংখ্যা O(n²), তাই একেকটির sum আলাদা করে গুনলে কাজ অনেক। দৃষ্টিভঙ্গি উল্টাও: প্রতিটা element-কে জিজ্ঞেস করো — "তুমি মোট কয়টা subarray-তে আছ?" যে যতবার আছে, মোট sum-এ সে ততবার নিজের মান জমা দেয়।

a[i] কয়টা subarray-তে? Subarray-টার শুরু হতে হবে i-এর বাঁয়ে বা i-তে — option i + 1টা (index 0..i)। শেষ হতে হবে i-তে বা ডানে — option n - iটা (index i..n-1)। স্বাধীন পছন্দ, তাই গুণ:

মাঝের y-কে রাখতে বাঁ ও ডান সীমা বাছাই

1. n = 3, i = 1

   0x

   চিহ্নিত ঘর: 1y↑ i

   2z

   শুরু 0 বা 1; শেষ 1 বা 2। স্বাধীন দুই পছন্দে 2 × 2 = 4টি subarray।

চারটি subarray: [x,y], [x,y,z], [y], [y,z]। প্রতিটিতেই y ঠিক একবার আছে।

Python

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

মান 1 কতটি subarray-এর minimum?

1. i = 1; দুই পাশেই সব মান বড়

   03

   চিহ্নিত ঘর: 11↑ i

   22

   34

   বাঁয়ে শুরুর পছন্দ 0 বা 1; ডানে শেষের পছন্দ 1, 2 বা 3। মোট 2 × 3 = 6।

Subarray ছয়টি: [1], [3,1], [1,2], [3,1,2], [1,2,4], [3,1,2,4]। তাই 1-এর contribution 1×6=6। সমান minimum একাধিক হলে tie-breaking দিয়ে একই subarray দুবার গোনা ঠেকাতে হয়।

এখানে শুধু কাঠামোটা নাও: 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 করে বাঁ থেকে ডানে "ঝাড়ু" চালাও:

Python

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 বানানো	P[i+1] = P[i] + a[i]; শুরুতে P[0] = 0
Inclusive [l,r]-এর যোগ	P[r+1] - P[l]
Inclusive [l,r]-এ update	diff[l] += x; diff[r+1] -= x; শেষে prefix pass
Inclusive [l,r]-এর XOR	PX[r+1] ^ PX[l]
2D query	পুরোটা − ওপরের strip − বাঁয়ের strip + কোণা
Sum = K গোনা	শুরুতে seen[0]=1; প্রতি ধাপে seen[P-K] যোগ
K দিয়ে বিভাজ্য sum	একই remainder-র আগের prefix গোনা
Contribution	a[i] আছে (i+1) * (n-i)টি subarray-তে
Sweep line	শুরুর +1 ও শেষের −1 event সাজিয়ে চলমান count

প্রতিটা লাইনের পেছনে একটা ছবি আছে — ফিতা, সাইনবোর্ড, rectangle, জোড়া remainder, বাঁ-ডান পছন্দ। Formula ভুলে গেলে ছবিতে ফেরো — formula নিজেই ফিরে আসবে।