# Problems — Level 5: Prefix, Difference, Contribution

> এই folder-এ Level 5-এর 14টা problem-এর নোট আছে। প্রতিটার জন্য আলাদা `.md` file — নিজের ভাষায় problem বোঝা, ফিতা/দাগের ছবি, dry run, code আর ভুল থেকে শেখা।

## কীভাবে problem গুলো use করবে?

প্রতিটা problem-এর note লেখা হয় [../../../templates/math-problem-note-template.md](../../../templates/math-problem-note-template.md) follow করে — ২০টা section-এর template: problem বোঝা → brute force → optimization → dry run → complexity → "ভবিষ্যতের আমাকে এক লাইনে কী বলব"। শুরুতে template-টা একবার পড়ে নাও।

নিয়মটা সহজ:

1. Table থেকে problem নাও (recommended order [../README.md](../README.md)-তে)
2. আগে brute force ভাবো (এই level-এ প্রায় সবসময় O(n²) একটা সরল পথ আছে), তারপর নিজে খুঁজে দেখো কোন হিসাব বারবার হচ্ছে — সেটাই precompute-এর জায়গা
3. তারপর বিদ্যমান নোট পড়ো, নিজের approach মেলাও
4. নিজে সমাধান করার অগ্রগতি আলাদা খাতায় বা tracker-এ রাখো। “নোট আছে” কেবল ব্যাখ্যার উপস্থিতি বোঝায়।

## Tracker table

| # | Problem | Difficulty | Pattern | Inherits from | Source | Note file | নোটের অবস্থা |
| --- | --- | --- | --- | --- | --- | --- | --- |
| 067 | Prefix Sum | Easy | 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> | [067-prefix-sum.md](067-prefix-sum.md) | নোট আছে |
| 068 | Range Sum Query | Easy | P[r]-P[l-1] | 067 | একই source 067-এর মতো | [068-range-sum-query.md](068-range-sum-query.md) | নোট আছে |
| 069 | Difference Array | Medium | range update | 067 | Classic technique (USACO Guide silver) | [069-difference-array.md](069-difference-array.md) | নোট আছে |
| 070 | Range Update Query | Medium | diff + prefix | 069 | Classic exercise | [070-range-update-query.md](070-range-update-query.md) | নোট আছে |
| 071 | Prefix XOR | Medium | XOR prefix | 067, 060 | CSES Range Xor Queries — <https://cses.fi/problemset/task/1650> | [071-prefix-xor.md](071-prefix-xor.md) | নোট আছে |
| 072 | 2D Prefix Sum | Medium | rectangle I-E | 067, 044 | LeetCode Range Sum Query 2D — <https://leetcode.com/problems/range-sum-query-2d-immutable/>, CSES Forest Queries — <https://cses.fi/problemset/task/1652> | [072-2d-prefix-sum.md](072-2d-prefix-sum.md) | নোট আছে |
| 073 | Subarray Sum Equals K | Medium | prefix + hash map | 067 | LeetCode — <https://leetcode.com/problems/subarray-sum-equals-k/> | [073-subarray-sum-equals-k.md](073-subarray-sum-equals-k.md) | নোট আছে |
| 074 | Count Subarrays Divisible by K | Medium | prefix mod count | 073, 026 | LeetCode Subarray Sums Divisible by K — <https://leetcode.com/problems/subarray-sums-divisible-by-k/>, CSES Subarray Divisibility — <https://cses.fi/problemset/task/1662> | [074-subarrays-divisible-by-k.md](074-subarrays-divisible-by-k.md) | নোট আছে |
| 075 | Contribution Technique Basic | Medium | per-element counting | 045 | Classic CP technique | [075-contribution-technique-basic.md](075-contribution-technique-basic.md) | নোট আছে |
| 076 | Sum of All Subarrays | Medium | (i+1)*(n-i) | 075 | Classic CP exercise | [076-sum-of-all-subarrays.md](076-sum-of-all-subarrays.md) | নোট আছে |
| 077 | Sum of Subarray Minimums | Hard | contribution + spans | 076 | LeetCode — <https://leetcode.com/problems/sum-of-subarray-minimums/> | [077-sum-of-subarray-minimums.md](077-sum-of-subarray-minimums.md) | নোট আছে |
| 078 | Pair Contribution Problems | Medium | per-pair counting | 075 | Classic CP exercise | [078-pair-contribution-problems.md](078-pair-contribution-problems.md) | নোট আছে |
| 079 | Imos Method Basic | Medium | event difference | 069 | Classic technique (imos method) | [079-imos-method-basic.md](079-imos-method-basic.md) | নোট আছে |
| 080 | Sweep Line Intro | Medium | +1/-1 events | 079 | Classic technique | [080-sweep-line-intro.md](080-sweep-line-intro.md) | নোট আছে |

## "Inherits from" column-টা কী?

প্রতিটা problem আগের কারো কাঁধে দাঁড়িয়ে। 067-এর running total থেকেই 068-এর query; 069-এর difference থেকে 070-এর full pipeline আর 079-এর imos; 073-এর hash map চাল 074-এ mod-এর পোশাকে ফেরে। আটকে গেলে "Inherits from" problem-টা আবার দেখো।

```text
067 (prefix build) ──> 068 (range query)
   ├──> 069 (difference) ──> 070 (update pipeline) 
   │         └──> 079 (imos) ──> 080 (sweep line)
   ├──> 071 (prefix XOR)        [+ Level 4-এর 060]
   ├──> 072 (2D prefix)         [+ Level 3-এর 044 inclusion-exclusion]
   └──> 073 (sum = K) ──> 074 (divisible by K)   [+ Level 2-এর 026 mod]

075 (contribution) ──> 076 (sum of subarrays) ──> 077 (subarray minimums)
   └──> 078 (pair contribution)
```

## একটা ছোট পরামর্শ

এই level-এ প্রতিটা problem-এ দুটো প্রশ্ন নিজেকে করো: **"কোন হিসাবটা বারবার করছি?"** আর **"প্রশ্নটা উল্টে দিলে সহজ হয় কি?"** প্রথমটার উত্তর prefix/difference, দ্বিতীয়টার উত্তর contribution। আর dry run-এ ফাঁকি দিও না — prefix problem-এর সব bug হলো off-by-one, আর off-by-one ধরা পড়ে শুধু হাতে-চালানো ছোট উদাহরণে।

Concept ঝালাই করতে → [../concept-notes.md](../concept-notes.md)। ছবি এঁকে বুঝতে → [../visualization-ideas.md](../visualization-ideas.md)।