# 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 দেখবে।

পড়ার ক্রম: এই পরিচয় → নিচের বিস্তারিত ধারণা → [চিত্রে হাতে-কলমে হিসাব](visualization-ideas.md) → [সমস্যার তালিকা](problems/README.md)। প্রতিটি উদাহরণে আগে 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 বের করা হলো **ফিতা কাটার** মতো — পুরো ফিতা থেকে বাঁ দিকের অপ্রয়োজনীয় টুকরো কেটে ফেলো:

```dsa
kind: array
title: "প্রথম চারটির যোগ থেকে প্রথমটির যোগ বাদ"
steps:
  - label: "Array: index 1 থেকে 3 পর্যন্ত চাই"
    values: [2, 5, 1, 3, 4]
    active: [1, 2, 3]
    pointers: {L: 1, R: 3}
    note: "নির্বাচিত মান 5 + 1 + 3 = 9।"
  - label: "Prefix: সীমা দুটির মোট"
    values: [0, 2, 7, 8, 11, 15]
    active: [1, 4]
    pointers: {L: 1, "R+1": 4}
    note: "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:

```dsa
kind: array
title: "দুই update-এর চারটি সীমানা, শেষে একটি prefix pass"
steps:
  - label: "১. Index 1 থেকে 3-এ +10"
    values: [0, 10, 0, 0, -10, 0]
    active: [1, 4]
    note: "Index 1-এ চালু, index 4-এ বন্ধ। Index 5 হলো অতিরিক্ত sentinel।"
  - label: "২. Index 2 থেকে 4-এ +5"
    values: [0, 10, 5, 0, -10, -5]
    active: [2, 5]
    note: "আগের দাগ রেখে নতুন শুরু ও শেষের দাগ যোগ করি।"
  - label: "৩. বাঁ থেকে চলমান যোগ = চূড়ান্ত array"
    values: [0, 10, 15, 15, 5]
    active: [2, 3]
    note: "দুটি 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-র ছবি:

```dsa
kind: grid
title: "নিচের ডানের 2×2 অংশের যোগ চাই"
steps:
  - label: "সারি 1–2, কলাম 1–2; সূচক শূন্য থেকে"
    rows: [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
    active: [[1, 1], [1, 2], [2, 1], [2, 2]]
    muted: [[0, 0], [0, 1], [0, 2], [1, 0], [2, 0]]
    note: "চাই 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/](../../05-hashing/README.md))।

```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)। স্বাধীন পছন্দ, তাই গুণ:

```dsa
kind: array
title: "মাঝের y-কে রাখতে বাঁ ও ডান সীমা বাছাই"
steps:
  - label: "n = 3, i = 1"
    values: [x, y, z]
    active: [1]
    pointers: {i: 1}
    note: "শুরু 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/](../../04-stack-and-queue/README.md)।

```dsa
kind: array
title: "মান 1 কতটি subarray-এর minimum?"
steps:
  - label: "i = 1; দুই পাশেই সব মান বড়"
    values: [3, 1, 2, 4]
    active: [1]
    pointers: {i: 1}
    note: "বাঁয়ে শুরুর পছন্দ 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 নিজেই ফিরে আসবে।