Problem link ও উৎস
- **Original source:** Classic CP exercise (sum over all subarrays via contribution)
- **Platform:** Classic CP exercise —
- **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
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#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 ধরে যোগ না করে।
### Input ও output {#6-example-input-and-output}
```text
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 ঋণাত্মকও হতে পারে, যোগফলে তা ঠিকঠাক প্রতিফলিত।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো একটা ভোটে কয়েকজন প্রার্থী, আর অনেকগুলো আলাদা panel (subarray) সাজানো হচ্ছে পরপর প্রার্থীদের নিয়ে। প্রতিটা panel-এর "মোট জনপ্রিয়তা" = সেই panel-এর প্রার্থীদের জনপ্রিয়তার যোগফল। তুমি জানতে চাও — সব panel-এর জনপ্রিয়তা মিলিয়ে মোট কত?
প্রতিটা panel আলাদা করে যোগ করা ক্লান্তিকর। বরং প্রতিটা প্রার্থীকে জিজ্ঞেস করো: "তুমি মোট কয়টা panel-এ আছ?" সে যত panel-এ আছে, তার জনপ্রিয়তা ঠিক ততবার মোটে যোগ হবে। তাই মোট = প্রতিটা প্রার্থীর (জনপ্রিয়তা × কয়টা panel-এ আছে)-এর যোগফল।
এই "প্রতিটা panel না, প্রতিটা প্রার্থী" দৃষ্টিভঙ্গিই contribution technique। element = প্রার্থী, subarray = panel, মান = জনপ্রিয়তা।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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)` রহস্যময় মনে হবে।
### ভেতরের অঙ্ক {#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)`। তাই:
```text
সব 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)-এ নামায়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সব subarray-র sum আলাদা বের করে যোগ। running sum দিয়ে একটু চটপট:
```python
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²)**।
```text
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]` দিয়ে গুণ করে সব যোগ:
```python
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) আরও শক্তিশালী রূপে ফিরবে।
### ছবিতে বোঝা {#5-visual-explanation}
`a = [1, 2, 3]`, n = 3। প্রতিটা element কয়টা subarray-তে, আর তার অবদান:
```text
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 ধরে:
```text
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 ঘোরা লাগল না।
### ছোট input-এ ধাপে ধাপে {#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বার) যোগ হলো — তাই তার অবদানই বড়।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
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}
```text
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(...)` সব অবদান যোগ করে চূড়ান্ত উত্তর দেয়।
```text
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!`।
### Output মিলিয়ে দেখা {#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:
```text
20
56
সব test pass!
```
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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 এমনিতেই সামলায়, কিন্তু যাচাই করো।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **078 (Pair Contribution Problems)** — element-এর বদলে pair-এর contribution (পরের ধাপ এই repo-তে)।
- **LeetCode — Sum of Subarray Minimums** (