Skip to content

Problems — Level 5: Prefix, Difference, Contribution

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

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

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

নিয়মটা সহজ:

  1. Table থেকে problem নাও (recommended order ../README.md-তে)
  2. আগে brute force ভাবো (এই level-এ প্রায় সবসময় O(n²) একটা সরল পথ আছে), তারপর নিজে খুঁজে দেখো কোন হিসাব বারবার হচ্ছে — সেটাই precompute-এর জায়গা
  3. তারপর note file বানাও/পড়ো, নিজের approach মেলাও
  4. Solve হলে Status planned → done

Tracker table

# Problem Difficulty Pattern Inherits from Source Note file Status
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 planned
068 Range Sum Query Easy P[r]-P[l-1] 067 একই source 067-এর মতো 068-range-sum-query.md planned
069 Difference Array Medium range update 067 Classic technique (USACO Guide silver) 069-difference-array.md planned
070 Range Update Query Medium diff + prefix 069 Classic exercise 070-range-update-query.md planned
071 Prefix XOR Medium XOR prefix 067, 060 CSES Range Xor Queries — https://cses.fi/problemset/task/1650 071-prefix-xor.md planned
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 planned
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 planned
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 planned
075 Contribution Technique Basic Medium per-element counting 045 Classic CP technique 075-contribution-technique-basic.md planned
076 Sum of All Subarrays Medium (i+1)*(n-i) 075 Classic CP exercise 076-sum-of-all-subarrays.md planned
077 Sum of Subarray Minimums Hard contribution + spans 076 LeetCode — https://leetcode.com/problems/sum-of-subarray-minimums/ 077-sum-of-subarray-minimums.md planned
078 Pair Contribution Problems Medium per-pair counting 075 Classic CP exercise 078-pair-contribution-problems.md planned
079 Imos Method Basic Medium event difference 069 Classic technique (imos method) 079-imos-method-basic.md planned
080 Sweep Line Intro Medium +1/-1 events 079 Classic technique 080-sweep-line-intro.md planned

"Inherits from" column-টা কী?

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

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। ছবি এঁকে বুঝতে → ../visualization-ideas.md।