076 — Sum of All Subarrays

075-এ গুনলে প্রতিটা element কয়টা subarray-তে আছে। এবার সেই গোনাটা আসল কাজে লাগাব: সব subarray-র sum-এর মোট যোগফল। চাবিটা সরল কিন্তু সুন্দর — যে element যতবার appear করে, মোট sum-এ সে ততবার নিজের মান জমা দেয়। তাই প্রতিটা subarray-র sum আলাদা করে বের করার দরকার নেই; প্রতিটা element-এর contribution যোগ করলেই হলো। ধীরে পড়ো।

Source

• Original source: Classic CP exercise (sum over all subarrays via contribution)
• Platform: Classic CP exercise — https://usaco.guide/silver/more-prefix-sums
• Topic: Math-based programming fundamentals → Level 5: Prefix, Difference, Contribution
• Difficulty: Medium
• Pattern: contribution technique — sum of all subarrays via (i+1)*(n-i)
• Basic idea inherited from: 075 — Contribution Technique Basic

1. Problem in simple words

একটা array a (দৈর্ঘ্য n) দেওয়া। তোমাকে বলতে হবে — সব সম্ভাব্য contiguous subarray-র sum আলাদা আলাদা বের করে, সেই sum গুলোর মোট যোগফল কত?

যেমন a = [1, 2, 3]-এর subarray গুলো: [1], [2], [3], [1,2], [2,3], [1,2,3] — এদের sum যথাক্রমে 1, 2, 3, 3, 5, 6। মোট = 1+2+3+3+5+6 = 20। তোমার কাজ এই 20 দ্রুত বের করা — প্রতিটা subarray ধরে যোগ না করে।

2. What is the math idea?

মূল idea হলো contribution technique — প্রতিটা element মোট sum-এ কতটা যোগ করে সেটা গোনা।

a[i] যতগুলো subarray-তে আছে, প্রতিটায় সে নিজের মান একবার করে যোগ করে। তাই মোট sum-এ a[i]-এর অবদান = a[i] × (কয়টা subarray-তে আছে)। 075 থেকে জানি সেই গোনা (i+1)*(n-i)। তাই:

সব subarray-র sum-এর যোগফল = Σ  a[i] * (i + 1) * (n - i)
                              i=0..n-1

মানে subarray ধরে না গুনে element ধরে গুনছি — প্রতিটা element-এর contribution জমাচ্ছি। rule of product (075) এখানে rule of sum-এর সাথে মিলে কাজটা O(n)-এ নামায়।

3. Which basic idea does this inherit from?

সরাসরি 075 (Contribution Technique Basic) থেকে। 075-এ শিখেছি index i আছে (i+1)*(n-i) টা subarray-তে। এখানে সেই count-কে a[i] দিয়ে গুণ করে যোগ করছি।

075 ছিল "গোনা" (কয়টা subarray-তে আছ), 076 হলো "গোনাকে কাজে লাগানো" (সেই appearances থেকে মোট অবদান)। দুটো মিলে contribution technique-এর পূর্ণ গল্প — আর এটাই "sum over all subarrays" ঘরানার সব problem-এর template। 075 না বুঝলে এখানকার (i+1)*(n-i) রহস্যময় মনে হবে।

4. Real-life analogy

ভাবো একটা ভোটে কয়েকজন প্রার্থী, আর অনেকগুলো আলাদা panel (subarray) সাজানো হচ্ছে পরপর প্রার্থীদের নিয়ে। প্রতিটা panel-এর "মোট জনপ্রিয়তা" = সেই panel-এর প্রার্থীদের জনপ্রিয়তার যোগফল। তুমি জানতে চাও — সব panel-এর জনপ্রিয়তা মিলিয়ে মোট কত?

প্রতিটা panel আলাদা করে যোগ করা ক্লান্তিকর। বরং প্রতিটা প্রার্থীকে জিজ্ঞেস করো: "তুমি মোট কয়টা panel-এ আছ?" সে যত panel-এ আছে, তার জনপ্রিয়তা ঠিক ততবার মোটে যোগ হবে। তাই মোট = প্রতিটা প্রার্থীর (জনপ্রিয়তা × কয়টা panel-এ আছে)-এর যোগফল।

এই "প্রতিটা panel না, প্রতিটা প্রার্থী" দৃষ্টিভঙ্গিই contribution technique। element = প্রার্থী, subarray = panel, মান = জনপ্রিয়তা।

5. Visual explanation

a = [1, 2, 3], n = 3। প্রতিটা element কয়টা subarray-তে, আর তার অবদান:

index i:           0     1     2
a[i]:              1     2     3
count (i+1)(n-i):  3     4     3      ← 075 থেকে
অবদান a[i]×count:  3     8     9      ← এই element মোট sum-এ যত যোগ করে

মোট = 3 + 8 + 9 = 20

মিলিয়ে দেখো subarray ধরে:

subarray      sum
---------------------
[1]            1
[2]            2
[3]            3
[1,2]          3
[2,3]          5
[1,2,3]        6
---------------------
মোট           20      ✓ একই উত্তর!

মূল কথা: element 2 আছে 4টা subarray-তে ([2],[1,2],[2,3],[1,2,3]), তাই মোট sum-এ 2 যোগ হয় 4 বার = 8। প্রতিটা element-এর এই appearance-গুনে-মান জমালেই পুরো যোগফল — subarray ঘোরা লাগল না।

6. Example input and output

a = [1, 2, 3]        -> 20      (Σ a[i]*(i+1)*(n-i) = 1·3 + 2·4 + 3·3)
a = [4]              -> 4       (একটাই subarray [4])
a = [1, 2, 3, 4]     -> 50
a = [2, 5, 1, 3]     -> 56
a = [-1, 2, -3]      -> -4      (negative-ও ঠিক চলে)

Edge case: একটা element হলে উত্তর সেই element নিজেই ([4] → 4)। আর negative সংখ্যাতেও সূত্র অবিকল কাজ করে — contribution ঋণাত্মকও হতে পারে, যোগফলে তা ঠিকঠাক প্রতিফলিত।

7. Brute force thinking

সব subarray-র sum আলাদা বের করে যোগ। running sum দিয়ে একটু চটপট:

def sum_all_subarrays_brute(a):
    n = len(a)
    total = 0
    for l in range(n):
        s = 0
        for r in range(l, n):
            s += a[r]          # subarray (l..r)-এর running sum
            total += s         # সেই sum মোটে যোগ
    return total

সরল, ঠিক উত্তর — প্রতিটা শুরু l-এর জন্য r বাড়িয়ে subarray-র sum জমায়, সেটা মোটে যোগ করে।

8. Why brute force may be slow

দুটো nested loop, প্রায় n²/2 subarray — O(n²)।

n = 50000 হলে:
  brute force: ~1.25 × 10^9 operation  (O(n²)) — TLE
  contribution: ~50000 operation       (এক pass, O(n))

অপচয়টা: একই element নানা subarray-তে বারবার যোগ হচ্ছে — অথচ "সে মোট কতবার যোগ হবে" এক সূত্রেই জানা যায়, প্রতিবার আলাদা যোগ না করে।

9. Better thinking

মূল insight: প্রতিটা subarray-র sum না বের করে, প্রতিটা element মোটে কতবার যোগ হবে গোনো — সেটা (i+1)*(n-i) (075)। তারপর a[i] দিয়ে গুণ করে সব যোগ:

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

প্রতিটা element-এ একটা গুণ — মোট O(n)। O(n²) থেকে নেমে এল, শুধু দৃষ্টিভঙ্গি উল্টে।

10. Thinking tweak

আসল "আহা!" মুহূর্ত: মোট যোগফলকে subarray ধরে না ভেঙে, element ধরে ভাঙো — "প্রতিটা টুকরো মোটে কত যোগ করে?" প্রতিটা a[i] ঠিক (i+1)*(n-i) বার যোগ হয়, তাই তার অবদান a[i]*(i+1)*(n-i)।

এই "প্রশ্ন উল্টে দাও" — subarray-গোনা থেকে element-অবদানে — হলো contribution technique-এর মূল মন্ত্র, যা 075 থেকে এসে এখানে আসল ফল দিল। একই চিন্তা pair নিয়ে (078) আর minimum নিয়ে (077) আরও শক্তিশালী রূপে ফিরবে।

11. Step-by-step dry run

a = [2, 5, 1, 3], n = 4। প্রতিটা element-এর অবদান:

i	a[i]	(i+1)	(n-i)	count = (i+1)(n-i)	অবদান = a[i]·count
0	2	1	4	4	2 × 4 = 8
1	5	2	3	6	5 × 6 = 30
2	1	3	2	6	1 × 6 = 6
3	3	4	1	4	3 × 4 = 12

মোট = 8 + 30 + 6 + 12 = 56। brute force-ও 56 দেয় ✓। element 5 মাঝখানে বলে সবচেয়ে বেশি (6বার) যোগ হলো — তাই তার অবদানই বড়।

12. Python solution

def sum_all_subarrays(a):
    """সব contiguous subarray-র sum-এর যোগফল; contribution technique, O(n)।
    প্রতিটা a[i] ঠিক (i+1)*(n-i) বার যোগ হয়।"""
    n = len(a)
    return sum(a[i] * (i + 1) * (n - i) for i in range(n))


def sum_all_subarrays_brute(a):
    """ধীর O(n^2) version — প্রতিটা subarray-র sum যোগ; মিলিয়ে দেখার জন্য।"""
    n = len(a)
    total = 0
    for l in range(n):
        s = 0
        for r in range(l, n):
            s += a[r]
            total += s
    return total


# --- ছোট test গুলো (সব pass করা উচিত) ---
assert sum_all_subarrays([1, 2, 3]) == 20
assert sum_all_subarrays([4]) == 4
assert sum_all_subarrays([1, 2, 3, 4]) == 50
assert sum_all_subarrays([2, 5, 1, 3]) == 56
assert sum_all_subarrays([-1, 2, -3]) == -4      # negative-ও ঠিক
assert sum_all_subarrays([]) == 0                # খালি array → 0

# fast আর brute একই উত্তর কিনা (random brute-force cross-check):
import random
random.seed(23)
for _ in range(500):
    arr = [random.randint(-9, 9) for _ in range(random.randint(0, 12))]
    assert sum_all_subarrays(arr) == sum_all_subarrays_brute(arr)

print(sum_all_subarrays([1, 2, 3]))      # 20
print(sum_all_subarrays([2, 5, 1, 3]))   # 56
print("সব test pass!")

13. Line-by-line explanation

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

পুরো সমাধান এক লাইনে। প্রতিটা index i-এর জন্য: a[i] = element-এর মান, (i+1)*(n-i) = সে কয়টা subarray-তে আছে (075)। গুণ করলে তার মোট অবদান; sum(...) সব অবদান যোগ করে চূড়ান্ত উত্তর দেয়।

for l in range(n):
    s = 0
    for r in range(l, n):
        s += a[r]
        total += s

ধীর brute — প্রতিটা subarray (l..r)-এর sum running-ভাবে বের করে মোটে যোগ। শুধু সূত্র মিলিয়ে দেখার জন্য।

বাকি assert গুলো নির্দিষ্ট উদাহরণ + random array-তে fast আর brute মিলিয়ে দেখছে (brute-force cross-check), negative ও খালি array সহ। সব মিললে সব test pass!।

14. Output walkthrough

a = [1, 2, 3]:

• i=0: 1 × 1 × 3 = 3
• i=1: 2 × 2 × 2 = 8
• i=2: 3 × 3 × 1 = 9
• যোগফল 3 + 8 + 9 = 20 → প্রথম print
• [2,5,1,3] → 8 + 30 + 6 + 12 = 56 → দ্বিতীয় print
• সব assert pass → সব test pass!

ছাপা output:

20
56
সব test pass!

15. Time complexity

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

16. Space complexity

O(1) — শুধু একটা চলমান যোগফল রাখছি (generator-এ একটার পর একটা term)। কোনো বাড়তি array লাগছে না।

17. Common mistakes

1. count আর মান গুলিয়ে ফেলা — অবদান = a[i] × (i+1)*(n-i); শুধু count যোগ করলে (মান বাদ দিলে) ভুল।
2. (i+1)*(n-i) সূত্র ভুল লেখা — 075-এর মতোই: বাঁয়ে i+1, ডানে n-i। ছবি আঁকো।
3. negative ভুলে int overflow ভাবা (অন্য ভাষায়) — Python-এ overflow নেই, কিন্তু C++/Java-তে বড় n-এ যোগফল long long লাগে; এখানে নিশ্চিন্ত, কিন্তু মনে রাখো।
4. subarray-র sum প্রতিবার গোড়া থেকে যোগ করা (brute-এও) — running sum না রাখলে brute O(n³) হয়; এমনিতেও brute বাদ দিয়ে সূত্র ব্যবহার করো।
5. খালি array — []-এর উত্তর 0; generator খালি হলে sum 0 দেয়, তাই code এমনিতেই সামলায়, কিন্তু যাচাই করো।

18. Harder problems that inherit this idea

• 078 (Pair Contribution Problems) — element-এর বদলে pair-এর contribution (পরের ধাপ এই repo-তে)।
• LeetCode — Sum of Subarray Minimums (https://leetcode.com/problems/sum-of-subarray-minimums/) — প্রতিটা element কতগুলো subarray-তে minimum, সেই span-গোনা (077)।
• LeetCode — Sum of Subarray Ranges (https://leetcode.com/problems/sum-of-subarray-ranges/) — max-contribution − min-contribution; এই idea-র যুগল প্রয়োগ।

19. Pattern learned

Sum over all subarrays via contribution — মোট = Σ a[i]*(i+1)*(n-i)। বড় শিক্ষা: প্রতিটা subarray-র sum বের কোরো না; প্রতিটা element মোটে কতবার যোগ হয় গোনো (appearances), মান দিয়ে গুণ করে জমাও — O(n²) নেমে আসে O(n)-এ।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "সব subarray-র sum-এর যোগফল = Σ a[i]*(i+1)*(n-i)। প্রতিটা element তার appearances-সংখ্যা বার যোগ হয়। subarray ঘুরো না, contribution জমাও — O(n)।"

পরের ধাপ → 077 — Sum of Subarray Minimums (এই level-এর সবচেয়ে কঠিন: contribution + "কতদূর পর্যন্ত আমি minimum")।

ফিরে দেখা: শিকড় → 075 — Contribution Technique Basic · এই 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" লেখো।