075 — Contribution Technique Basic

এতক্ষণ prefix/difference দিয়ে "একই হিসাব বারবার কোরো না" শিখলে। এবার সম্পূর্ণ নতুন একটা চিন্তার মোচড়: প্রশ্নটাই উল্টে দাও। subarray ধরে ধরে না গুনে, প্রতিটা element-কে জিজ্ঞেস করো — "তুমি মোট কয়টা subarray-তে আছ?" এই একটা প্রশ্নের উত্তর (i+1)*(n-i) — বাঁয়ে কত পছন্দ, ডানে কত পছন্দ। ছবিটা আঁকতে পারলে contribution-এর পুরো জগত খুলে যাবে।

Source

• Original source: Classic CP technique (contribution / per-element counting)
• Platform: Classic CP technique — https://usaco.guide/silver/more-prefix-sums
• Topic: Math-based programming fundamentals → Level 5: Prefix, Difference, Contribution
• Difficulty: Medium
• Pattern: contribution technique (count subarrays containing each index)
• Basic idea inherited from: 045 — counting / combinatorics basics

1. Problem in simple words

একটা array a (দৈর্ঘ্য n) দেওয়া। প্রতিটা index i-এর জন্য বলতে হবে — মোট কয়টা contiguous subarray-তে element a[i] আছে?

মানে কোনো মান যোগ-টোগ নয় এখনই; শুধু গোনা: index i-কে ঢাকে এমন subarray-র সংখ্যা। যেমন a = [1, 2, 3]-এ index 1 (মান 2) আছে 4টা subarray-তে: [2], [1,2], [2,3], [1,2,3]। এই গোনাটাই contribution technique-এর প্রথম ধাপ — পরের problem (076)-এ এই count দিয়ে আসল কাজ হবে।

2. What is the math idea?

মূল idea হলো per-element counting via independent choices (স্বাধীন পছন্দের গুণফল)।

একটা subarray ঠিক হয় দুটো জিনিসে: শুরুর index l আর শেষের index r। index i-কে ঢাকতে হলে l ≤ i ≤ r হতে হবে। তাহলে:

শুরু l বাছার option: 0, 1, ..., i        → (i + 1) টা
শেষ r বাছার option:  i, i+1, ..., n-1    → (n - i) টা

l আর r স্বাধীনভাবে বাছা যায়, তাই গুণ:

index i-কে ঢাকা subarray-র সংখ্যা = (i + 1) * (n - i)

এটা combinatorics-এর সরল গুণনীতি (rule of product): দুটো স্বাধীন পছন্দ মিলে মোট সংখ্যা = পছন্দ১ × পছন্দ২।

3. Which basic idea does this inherit from?

মূলত 045 (counting / combinatorics basics) থেকে — "স্বাধীন পছন্দ থাকলে গুণ করো" এই গুণনীতি। এখানে দুটো স্বাধীন পছন্দ: subarray-র বাঁ প্রান্ত আর ডান প্রান্ত।

prefix/difference থেকে এটা আলাদা চিন্তা — সেখানে "running total"; এখানে "কে কয়টায় আছে"। কিন্তু দুটোরই উদ্দেশ্য এক: O(n²) কাজকে O(n)-এ নামানো। contribution technique পুরো "sum over all subarrays" ঘরানার মাস্টার কী — আর তার ভিত্তি এই সহজ গোনা।

4. Real-life analogy

ভাবো একটা লম্বা ট্রেনে n টা বগি, পরপর সাজানো (index 0 থেকে n-1)। একটা "টিকিট" মানে পরপর কয়েকটা বগির একটা টানা অংশ — শুরুর বগি থেকে শেষের বগি পর্যন্ত।

তুমি জানতে চাও: বগি নম্বর i মোট কয়টা টিকিটে পড়ে? টিকিটের শুরু হতে হবে বগি i বা তার বাঁয়ে — মানে 0 থেকে i পর্যন্ত, (i+1) রকম শুরু। আর শেষ হতে হবে বগি i বা তার ডানে — i থেকে n-1 পর্যন্ত, (n-i) রকম শেষ।

শুরু আর শেষ আলাদাভাবে বাছাই, তাই মোট টিকিট = (i+1) × (n-i)। প্রতিটা বগির জন্য আলাদা করে গুনলে — মাঝের বগিগুলো বেশি টিকিটে পড়ে (বেশি option), প্রান্তের বগি কম।

5. Visual explanation

a = [1, 2, 3], n = 3। index 1 (মান 2)-কে কয়টা subarray ঢাকে?

index:     0     1     2
a:       [ 1 ] [ 2 ] [ 3 ]
                 ↑
            এই element কোথায় কোথায় আছে?

শুরু l বাছা (≤ 1):   l = 0  বা  l = 1     → 2 রকম  (i + 1 = 1 + 1 = 2)
শেষ  r বাছা (≥ 1):   r = 1, 2             → 2 রকম  (n - i = 3 - 1 = 2)

মোট = 2 × 2 = 4 টা subarray:
   l=0,r=1: [1,2]
   l=0,r=2: [1,2,3]
   l=1,r=1: [2]
   l=1,r=2: [2,3]            ✓ চারটাই index 1 ঢাকে

প্রতিটা index-এর জন্য count:

index i:           0     1     2
(i + 1):           1     2     3       ← বাঁয়ে শুরুর option
(n - i):           3     2     1       ← ডানে শেষের option
count = গুণ:        3     4     3       ← এই index কয়টা subarray-তে

মোট subarray = 3 + 4 + 3 = ... না! মোট subarray = n(n+1)/2 = 6।
(count-এর যোগফল ≠ subarray সংখ্যা; এটা "element-উপস্থিতি"-র যোগফল।)

মূল কথা: মাঝের index বেশি subarray-তে (বেশি option দুই পাশে), প্রান্তের কম। ছবিটা ধরো — বাঁয়ে পছন্দ × ডানে পছন্দ।

6. Example input and output

a = [1, 2, 3], n = 3
count per index = [3, 4, 3]    ((i+1)*(n-i))

a = [10], n = 1
count = [1]                    (একটাই subarray, একটাই element)

a = [5, 6, 7, 8], n = 4
count = [4, 6, 6, 4]           (1·4, 2·3, 3·2, 4·1)

a = [1, 1], n = 2
count = [2, 2]                 (1·2, 2·1)

লক্ষ করো count সবসময় symmetric (আয়নার মতো) — প্রান্ত থেকে কেন্দ্রের দিকে বাড়ে, কারণ কেন্দ্রের element-এর দুই পাশে বেশি জায়গা। আর count আসল মান a[i]-এর উপর নির্ভর করে না, শুধু position-এর উপর।

7. Brute force thinking

প্রতিটা index-এর জন্য সব subarray ঘুরে গুনি কোনগুলো ঢাকে:

def count_brute(a):
    n = len(a)
    counts = [0] * n
    for l in range(n):
        for r in range(l, n):     # প্রতিটা subarray (l..r)
            for i in range(l, r + 1):
                counts[i] += 1    # এই subarray যাদের ঢাকে, সবার count++
    return counts

সরল, ঠিক উত্তর দেয় — প্রতিটা subarray ধরে তার ভেতরের সব index-এর count বাড়ায়।

8. Why brute force may be slow

তিনটা nested loop! বাইরের দুটো subarray (n²/2 টা), ভেতরেরটা subarray-র দৈর্ঘ্য ধরে — মোট O(n³)। (এমনকি ভেতরের loop বাদ দিয়ে শুধু subarray গুনলেও O(n²)।)

n = 1000 হলে:
  brute force (O(n³)): ~10^9 operation  — খুব ধীর
  formula way (O(n)) : ~1000 operation  — চোখের পলকে

অপচয়টা স্পষ্ট: একই index বারবার গোনা হচ্ছে নানা subarray-তে। অথচ একটা সহজ সূত্রেই গোনার সংখ্যা সরাসরি বেরিয়ে আসে।

9. Better thinking

মূল insight: index i-কে গুনতে subarray ঘুরো না — শুধু গণনা করো কয়ভাবে বাঁ প্রান্ত আর ডান প্রান্ত বাছা যায়। (i+1) রকম শুরু, (n-i) রকম শেষ, স্বাধীন তাই গুণ:

def count_subarrays_with_index(a):
    n = len(a)
    return [(i + 1) * (n - i) for i in range(n)]

প্রতিটা index-এর জন্য একটা গুণ — মোট O(n)। O(n³) (বা O(n²)) থেকে নেমে এল এক সূত্রে।

10. Thinking tweak

আসল "আহা!" মুহূর্ত: subarray গুনতে subarray ঘুরো না — প্রতিটা element-কে জিজ্ঞেস করো "তুমি কয়টায় আছ?" দৃষ্টিভঙ্গি subarray থেকে element-এ সরালে গোনাটা দুটো স্বাধীন পছন্দের গুণফলে নেমে আসে।

আর সেই গুণফল মনে রাখার চাবি: (i + 1) * (n - i) — বাঁয়ে i+1 রকম শুরু (index 0 থেকে i), ডানে n-i রকম শেষ (index i থেকে n-1)। মুখস্থ কোরো না, ছবি আঁকো — কোন প্রান্তে কতগুলো option। এই "প্রশ্ন উল্টে দাও" tweak-টাই contribution technique-এর প্রাণ, যা 076-077-এ আসল কাজে লাগবে।

11. Step-by-step dry run

a = [5, 6, 7, 8], n = 4। প্রতিটা index-এর count:

i	i + 1 (বাঁ option)	n - i (ডান option)	count = (i+1)*(n-i)
0	1	4	1 × 4 = 4
1	2	3	2 × 3 = 6
2	3	2	3 × 2 = 6
3	4	1	4 × 1 = 4

ফল: [4, 6, 6, 4]। যাচাই index 1: subarray গুলো যেগুলো index 1 ঢাকে — শুরু {0,1} × শেষ {1,2,3} = 2×3 = 6টা ✓। symmetric pattern (4,6,6,4) চোখে পড়ছে।

12. Python solution

def count_subarrays_with_index(a):
    """প্রতিটা index i কয়টা subarray-তে আছে: (i+1)*(n-i)। O(n)।"""
    n = len(a)
    return [(i + 1) * (n - i) for i in range(n)]


def count_brute(a):
    """ধীর O(n^3) version — প্রতিটা subarray ধরে গোনা; মিলিয়ে দেখার জন্য।"""
    n = len(a)
    counts = [0] * n
    for l in range(n):
        for r in range(l, n):
            for i in range(l, r + 1):
                counts[i] += 1
    return counts


# --- ছোট test গুলো (সব pass করা উচিত) ---
assert count_subarrays_with_index([1, 2, 3]) == [3, 4, 3]
assert count_subarrays_with_index([10]) == [1]
assert count_subarrays_with_index([5, 6, 7, 8]) == [4, 6, 6, 4]
assert count_subarrays_with_index([1, 1]) == [2, 2]
assert count_subarrays_with_index([]) == []          # খালি array

# count আসল মানের উপর নির্ভর করে না, শুধু length-এর উপর:
assert count_subarrays_with_index([99, -7, 0]) == count_subarrays_with_index([1, 2, 3])

# fast আর brute একই উত্তর কিনা (brute-force cross-check):
for length in range(0, 9):
    arr = list(range(length))          # মান যাই হোক, count একই
    assert count_subarrays_with_index(arr) == count_brute(arr)

# প্রতিটা count-এর যোগফল = সব subarray-র মোট দৈর্ঘ্য (আরেকটা সঙ্গতি-চেক):
def total_length_brute(a):
    n = len(a); tot = 0
    for l in range(n):
        for r in range(l, n):
            tot += (r - l + 1)
    return tot
for length in range(0, 9):
    arr = list(range(length))
    assert sum(count_subarrays_with_index(arr)) == total_length_brute(arr)

print(count_subarrays_with_index([1, 2, 3]))      # [3, 4, 3]
print(count_subarrays_with_index([5, 6, 7, 8]))   # [4, 6, 6, 4]
print("সব test pass!")

13. Line-by-line explanation

n = len(a)
return [(i + 1) * (n - i) for i in range(n)]

পুরো সমাধান এক লাইনে। প্রতিটা index i-এর জন্য: (i + 1) = বাঁয়ে শুরু বাছার রকম (index 0 থেকে i), (n - i) = ডানে শেষ বাছার রকম (index i থেকে n-1)। স্বাধীন পছন্দ, তাই গুণ — সেটাই index i-কে ঢাকা subarray-র সংখ্যা।

for l in range(n):
    for r in range(l, n):
        for i in range(l, r + 1):
            counts[i] += 1

ধীর brute — প্রতিটা subarray (l..r) ধরে, তার ভেতরের সব index-এর count বাড়ায়। তিন স্তরের loop, শুধু সূত্র মিলিয়ে দেখার জন্য।

বাকি assert গুলো নির্দিষ্ট উদাহরণ + সব length-এ fast আর brute মিলিয়ে দেখছে (brute-force cross-check), আর দুটো সঙ্গতি-চেক: count আসল মান-নিরপেক্ষ, এবং count-এর যোগফল = সব subarray-র মোট দৈর্ঘ্য। সব মিললে সব test pass!।

14. Output walkthrough

a = [1, 2, 3]:

• i=0: 1 × 3 = 3
• i=1: 2 × 2 = 4
• i=2: 3 × 1 = 3
• ফল [3, 4, 3] → প্রথম print
• [5,6,7,8] → [4, 6, 6, 4] → দ্বিতীয় print
• সব assert pass → সব test pass!

ছাপা output:

[3, 4, 3]
[4, 6, 6, 4]
সব test pass!

15. Time complexity

O(n) — প্রতিটা index-এর জন্য একটা গুণ, n টা index। brute force-এর O(n³) (বা subarray-শুধু-গুনলে O(n²)) থেকে বিশাল উন্নতি।

16. Space complexity

O(n) — n দৈর্ঘ্যের count array ফেরত দিচ্ছি। শুধু count চাইলে এটুকুই; প্রতিটা আলাদা ছাপলে O(1) extra-ও সম্ভব।

17. Common mistakes

1. (i + 1) * (n - i) আর i * (n - i - 1) গুলিয়ে ফেলা — বাঁয়ে option i+1 (index 0..i), ডানে n-i (index i..n-1)। ছবি আঁকো, মুখস্থ কোরো না।
2. 0-indexing vs 1-indexing — এই সূত্র 0-indexed। 1-indexed হলে i * (n - i + 1) হয়; convention মিলিয়ে নাও।
3. count-এর যোগফল = subarray সংখ্যা ভাবা — না; count-এর যোগফল = সব subarray-র মোট দৈর্ঘ্য। subarray সংখ্যা আলাদা: n(n+1)/2।
4. count আসল মানের উপর নির্ভর ভাবা — count শুধু position-নির্ভর; a[i]-র মান এখানে অপ্রাসঙ্গিক (মান লাগবে 076-এ গুণ করার সময়)।
5. প্রান্ত off-by-one — index 0-এর বাঁয়ে শুরু মাত্র 1 রকম (নিজেই), index n-1-এর ডানে শেষ মাত্র 1 রকম; সূত্র এটা ঠিক দেয় কিনা প্রান্তে যাচাই করো।

18. Harder problems that inherit this idea

• 076 (Sum of All Subarrays) — এই count-কে a[i] দিয়ে গুণ করে সব subarray-র sum-এর যোগফল (পরের ধাপ)।
• 078 (Pair Contribution Problems) — element-এর বদলে pair ধরে একই "কে কয়টায় আছে" চিন্তা।
• LeetCode — Sum of Subarray Minimums (https://leetcode.com/problems/sum-of-subarray-minimums/) — contribution + span; এই গোনার কঠিন রূপ (077)।

19. Pattern learned

Contribution technique (per-element counting) — প্রতিটা index কয়টা subarray-তে আছে = (i+1)*(n-i) (বাঁ option × ডান option)। বড় শিক্ষা: subarray ঘুরে না গুনে প্রশ্নটা উল্টে দাও — প্রতিটা element-কে জিজ্ঞেস করো "তুমি কয়টায় আছ?"; দুটো স্বাধীন পছন্দের গুণফলেই উত্তর।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "contribution-এর ভিত্তি = index i আছে (i+1)*(n-i) টা subarray-তে (বাঁয়ে i+1 শুরু, ডানে n-i শেষ)। subarray ঘুরো না, প্রশ্ন উল্টে element গোনো — O(n)।"

পরের ধাপ → 076 — Sum of All Subarrays (এই count-কে a[i] দিয়ে গুণ করে সব subarray-র sum-এর যোগফল)।

ফিরে দেখা: এই level-এর map → ../README.md · concept ঝালাই → ../concept-notes.md · template → ../../../templates/math-problem-note-template.md।

---

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখো; problem statement copy কোরো না; official link শুধু attribution-এর জন্য রাখো; "asked by Google/Amazon" এমন দাবি কোরো না — বরং "Google-style pattern" / "common interview pattern" লেখো।