# Level 5 — Prefix, Difference, Contribution (আগে থেকে হিসেব করে রাখার জাদু)

[ধারণা](concept-notes.md) · [চিত্র ও উদাহরণ](visualization-ideas.md) · [সমস্যার তালিকা](problems/README.md) · [মূল উৎস](source-map.md) · [পুরো শেখার মানচিত্র](../roadmap.md)

> দোকানদার প্রতিবার গ্রাহক এলে গোটা খাতা যোগ করে না — সে একটা running total রাখে। এই level-এর পুরোটাই সেই বুদ্ধি: **একবার কষ্ট করে precompute করো, তারপর প্রতিটা query-র উত্তর দাও চোখের পলকে।** Prefix sum, difference array, আর contribution — তিনটা কৌশল, একটাই দর্শন: কাজটা আগেই করে রাখো।

## এই level এ কী শিখবে?

মূল idea গুলো:

- **Prefix sum** — running total-এর array; `sum(l..r) = P[r] - P[l-1]` — ফিতা কেটে মাপার ছবি
- **Difference array** — prefix sum-এর উল্টো অপারেশন; range update মানে শুধু দুই প্রান্তে দাগ (`l`-এ +x, `r+1`-এ -x)
- **Prefix XOR** — যোগের জায়গায় XOR বসালেও একই কৌশল চলে (Level 4-এর XOR ফিরে আসে!)
- **2D prefix sum** — rectangle-এর sum, inclusion-exclusion-এর ছবি দিয়ে
- **Prefix + hash map** — "P[r] - K কি আগে দেখেছি?" — subarray sum = K এক pass-এ
- **Prefix mod K** — divisible subarray গোনা; একই remainder-এর জোড়া মানেই উত্তর
- **Contribution technique** — subarray ধরে না গুনে প্রতিটা element-কে জিজ্ঞেস করা: "তুমি কয়টা subarray-তে আছ?"
- **Imos method আর sweep line** — event-ভিত্তিক +1/-1 দাগ দিয়ে timeline-এর হিসাব

## কেন এই level দরকার?

**Competitive programming (CP) এ:** prefix sum হলো CP-র সবচেয়ে বেশি ব্যবহৃত precomputation — CSES, Codeforces Div 2-এর A/B/C-তে এটা ছাড়া চলা যায় না। Difference array আর imos method ছাড়া range update problem-এ TLE নিশ্চিত। আর contribution technique হলো "sum over all subarrays" ঘরানার প্রতিটা problem-এর মাস্টার কী।

**Interview এ:** Subarray Sum Equals K হলো অন্যতম জনপ্রিয় interview problem — prefix + hash map-এর combo টা Two Sum-এরই বড় ভাই। Range Sum Query, 2D matrix sum, Sum of Subarray Minimums — সবগুলোই common interview pattern।

**পরের ধাপে:** sliding window (Level 6) আসলে prefix-চিন্তারই গতিশীল রূপ; segment tree আর BIT হলো prefix sum-এর "update-ও করা যায়" version; sweep line থেকে interval problem-এর পুরো জগত খোলে।

## Prerequisites

- [Level 0: Absolute Basics](../00-absolute-basics/README.md) — loop আর array-তে স্বচ্ছন্দ হওয়া
- [Level 2: Modular Arithmetic](../02-modular-arithmetic/README.md) — problem 074-এ `P mod K` লাগবে
- [Level 4: Bit Manipulation](../04-bit-manipulation/README.md) — problem 071-এ XOR-এর self-inverse ধর্ম লাগবে
- Hash map (Python `dict`) basics — problem 073/074-এ; গভীরে যেতে [../../05-hashing/](../../05-hashing/README.md) পরে আছে

## Learning goals (checklist)

এই level শেষে নিজেকে জিজ্ঞেস করো:

- [ ] Prefix array বানিয়ে `sum(l..r) = P[r] - P[l-1]` — off-by-one ভুল ছাড়া লিখতে পারি
- [ ] কেন `P[l-1]` বাদ দিতে হয় (l না) — ফিতার ছবি এঁকে বলতে পারি
- [ ] Difference array-তে একটা range update মানে ঠিক 2টা লেখা — এই দাবিটা ব্যাখ্যা করতে পারি
- [ ] Prefix XOR দিয়ে range XOR query — যোগের বদলে XOR কেন একই template-এ চলে, জানি
- [ ] 2D prefix-এর 4-term formula (inclusion-exclusion) ছবি দেখে নিজে বের করতে পারি
- [ ] Subarray Sum = K-তে hash map-এ কী রাখি, কখন count বাড়াই — পরিষ্কার
- [ ] `prefix[0] = 0`-এর base entry (hash map-এ `{0: 1}`) কেন লাগে, বুঝি
- [ ] Contribution-এ `(i + 1) * (n - i)` formula-টা আঁকতে পারি — বাঁয়ে কত পছন্দ, ডানে কত পছন্দ
- [ ] Imos method-এ event থেকে difference array — অন্তত একটা উদাহরণ হাতে চালিয়েছি
- [ ] Sweep line-এ +1/-1 event sort করে "একসাথে সর্বোচ্চ কয়জন" বের করতে পারি

## Problem list

মোট 14টা problem — 2টা Easy, 11টা Medium, 1টা Hard।

### Easy

| # | Problem | Pattern | Source |
| --- | --- | --- | --- |
| 067 | [Prefix Sum](problems/067-prefix-sum.md) | running total | LeetCode Range Sum Query Immutable — <https://leetcode.com/problems/range-sum-query-immutable/>, CSES Static Range Sum Queries — <https://cses.fi/problemset/task/1646> |
| 068 | [Range Sum Query](problems/068-range-sum-query.md) | P[r]-P[l-1] | একই source 067-এর মতো |

### Medium

| # | Problem | Pattern | Source |
| --- | --- | --- | --- |
| 069 | [Difference Array](problems/069-difference-array.md) | range update | Classic technique (USACO Guide silver) |
| 070 | [Range Update Query](problems/070-range-update-query.md) | diff + prefix | Classic exercise |
| 071 | [Prefix XOR](problems/071-prefix-xor.md) | XOR prefix | CSES Range Xor Queries — <https://cses.fi/problemset/task/1650> |
| 072 | [2D Prefix Sum](problems/072-2d-prefix-sum.md) | rectangle I-E | LeetCode Range Sum Query 2D — <https://leetcode.com/problems/range-sum-query-2d-immutable/>, CSES Forest Queries — <https://cses.fi/problemset/task/1652> |
| 073 | [Subarray Sum Equals K](problems/073-subarray-sum-equals-k.md) | prefix + hash map | LeetCode — <https://leetcode.com/problems/subarray-sum-equals-k/> |
| 074 | [Count Subarrays Divisible by K](problems/074-subarrays-divisible-by-k.md) | prefix mod count | LeetCode Subarray Sums Divisible by K — <https://leetcode.com/problems/subarray-sums-divisible-by-k/>, CSES Subarray Divisibility — <https://cses.fi/problemset/task/1662> |
| 075 | [Contribution Technique Basic](problems/075-contribution-technique-basic.md) | per-element counting | Classic CP technique |
| 076 | [Sum of All Subarrays](problems/076-sum-of-all-subarrays.md) | (i+1)*(n-i) | Classic CP exercise |
| 078 | [Pair Contribution Problems](problems/078-pair-contribution-problems.md) | per-pair counting | Classic CP exercise |
| 079 | [Imos Method Basic](problems/079-imos-method-basic.md) | event difference | Classic technique (imos method) |
| 080 | [Sweep Line Intro](problems/080-sweep-line-intro.md) | +1/-1 events | Classic technique |

### Hard

| # | Problem | Pattern | Source |
| --- | --- | --- | --- |
| 077 | [Sum of Subarray Minimums](problems/077-sum-of-subarray-minimums.md) | contribution + spans | LeetCode — <https://leetcode.com/problems/sum-of-subarray-minimums/> |

পুরো tracker table (status সহ) আছে [problems/README.md](problems/README.md)-তে।

## Recommended order

1. **067 → 068** — আগে running total বানাও, তারপর সেটা দিয়ে query-র উত্তর; এটাই পুরো level-এর ভিত
2. **069 → 070** — উল্টো দিক: query না, এবার update; difference array-র দুই-দাগের কৌশল
3. **071** — যোগের জায়গায় XOR বসিয়ে দেখো — template এক, operator ভিন্ন
4. **072** — এক dimension থেকে দুই dimension; inclusion-exclusion-এর ছবিটা এখানে আঁকতেই হবে
5. **073 → 074** — prefix-এর সাথে hash map-এর বিয়ে; 073 হলো এই level-এর তারকা problem
6. **075 → 076** — দৃষ্টিভঙ্গি উল্টাও: subarray না গুনে element গোনো
7. **078** — contribution-এর pair version
8. **077** — সবচেয়ে কঠিন; contribution + "কতদূর পর্যন্ত আমি minimum" — monotonic stack-এর গন্ধ
9. **079 → 080** — শেষে imos আর sweep line; difference-চিন্তা event-এর জগতে

## Common mistakes (সাধারণ ভুল)

1. **Off-by-one: `P[r] - P[l]` লিখে ফেলা** — l-তম element-টাও বাদ পড়ে যায়! বিয়োগ করতে হয় `P[l-1]` (0-indexed prefix-এ: `P[r+1] - P[l]`, যেখানে `P`-র দৈর্ঘ্য n+1)। Convention একটা বেছে নিয়ে সেটাতেই থাকো।
2. **`P[0] = 0`-এর sentinel ভুলে যাওয়া** — দৈর্ঘ্য n+1-এর prefix array না বানালে `l = 0`-এর query-তে আলাদা if লাগে; sentinel থাকলে formula সব জায়গায় এক।
3. **Hash map-এ `{0: 1}` initialize না করা** — Subarray Sum = K-তে যে subarray index 0 থেকে শুরু, সেটা গোনা হবে না। এটা এই problem-এর #1 bug।
4. **Difference array-তে `r+1` লিখতে ভুলে যাওয়া** — `diff[l] += x` দিলে `diff[r+1] -= x`-ও দিতে হবে, নইলে update টা array-র শেষ পর্যন্ত গড়িয়ে যায়। আর `r+1` যেন array-র বাইরে না যায় — সেজন্য diff-টা এক ঘর বড় রাখো।
5. **Python-এ negative mod নিয়ে নিশ্চিন্ত থেকে অন্য ভাষায় ফাঁদে পড়া** — Python-এ `-3 % 5 = 2` (সুবিধাজনক!), কিন্তু C++/Java-তে negative আসে। 074-এ remainder normalize করার অভ্যাসটা রাখো।
6. **Contribution-এ `(i + 1) * (n - i)` আর `i * (n - i - 1)` গুলিয়ে ফেলা** — শুরু বেছে নেওয়ার option `i + 1`টা (index 0 থেকে i), শেষ বেছে নেওয়ার option `n - i`টা (i থেকে n-1)। ছবি এঁকে নাও, মুখস্থ কোরো না।
7. **2D prefix-এ overlap দুবার বিয়োগ** — formula-তে `+ P[r1-1][c1-1]` ফেরত যোগ করতে ভুলে যাওয়া; inclusion-exclusion-এর কোণার ব্লকটা দুবার কাটা পড়ে, একবার ফেরত দিতে হয়।
8. **Difference আর prefix-এর ক্রম গুলিয়ে ফেলা** — সব update আগে শেষ করো, **তারপর** একবার prefix চালাও। মাঝপথে query এলে এই সরল কৌশল চলে না (তখন BIT/segment tree-র এলাকা)।

## পরের level এ যাওয়ার আগে checklist

- [ ] `[2, 5, 1, 3]`-এর prefix array হাতে বানিয়ে 2-3টা range query করেছি
- [ ] একটা difference array-তে 3টা range update দিয়ে শেষে prefix চালিয়ে উত্তর মিলিয়েছি
- [ ] 073-এর hash map-এর dry run খাতায় করেছি — প্রতি step-এ map-এ কী আছে লিখে
- [ ] `(i + 1) * (n - i)`-এর ছবি কাউকে বুঝিয়ে বলেছি (বাঁয়ে পছন্দ × ডানে পছন্দ)
- [ ] 2D prefix-এর 4-term formula ছবি না দেখে একবার লিখেছি
- [ ] Imos method দিয়ে অন্তত একটা "অনেক মানুষ আসে-যায়" type উদাহরণ হাতে চালিয়েছি

সব টিক দিতে পারলে — চলো [Level 6: Two Pointers ও Sliding Window](../06-two-pointers-sliding-window-math/README.md)-এ। সেখানে precompute নয় — দুটো আঙুল আর একটা জানালা দিয়ে array-র উপর হাঁটতে শিখবে।

## Source map

এই folder-এর প্রতিটা concept আর problem কোথা থেকে এসেছে, কোন link official, আর কোনটা original লেখা — সব হিসাব আছে [source-map.md](source-map.md)-তে।