Skip to content

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

দোকানদার প্রতিবার গ্রাহক এলে গোটা খাতা যোগ করে না — সে একটা 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

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 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 P[r]-P[l-1] একই source 067-এর মতো

Medium

# Problem Pattern Source
069 Difference Array range update Classic technique (USACO Guide silver)
070 Range Update Query diff + prefix Classic exercise
071 Prefix XOR XOR prefix CSES Range Xor Queries — https://cses.fi/problemset/task/1650
072 2D Prefix Sum 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 prefix + hash map LeetCode — https://leetcode.com/problems/subarray-sum-equals-k/
074 Count Subarrays Divisible by K 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 per-element counting Classic CP technique
076 Sum of All Subarrays (i+1)*(n-i) Classic CP exercise
078 Pair Contribution Problems per-pair counting Classic CP exercise
079 Imos Method Basic event difference Classic technique (imos method)
080 Sweep Line Intro +1/-1 events Classic technique

Hard

# Problem Pattern Source
077 Sum of Subarray Minimums contribution + spans LeetCode — https://leetcode.com/problems/sum-of-subarray-minimums/

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

  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-এ। সেখানে precompute নয় — দুটো আঙুল আর একটা জানালা দিয়ে array-র উপর হাঁটতে শিখবে।

Source map

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