Problem link ও উৎস
- **Original source:** LeetCode 315 — Count of Smaller Numbers After Self
- **Platform:** [LeetCode 315](https://leetcode.com/problems/count-of-smaller-numbers-after-self/)
- **Topic:** segment tree and fenwick tree
- **Difficulty:** Hard
- **Pattern:** BIT + coordinate compression
- **Basic idea inherited from:** BIT over values, sorting
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা array `a` দেওয়া। প্রতিটা index `i`-র জন্য বের করো: `i`-র **ডানদিকে** কতগুলো element আছে যেগুলো `a[i]`-এর চেয়ে **ছোট**। উত্তর একটা array `counts`, যেখানে `counts[i]` = ওই সংখ্যা।
```text
a = [5, 2, 6, 1]
counts = [2, 1, 1, 0]
a[0]=5 -> ডানে ছোট: {2, 1} -> 2
a[1]=2 -> ডানে ছোট: {1} -> 1
a[2]=6 -> ডানে ছোট: {1} -> 1
a[3]=1 -> ডানে ছোট: {} -> 0
```
### Input ও output {#8-example-input-and-output}
```text
input: a = [5, 2, 6, 1]
output: [2, 1, 1, 0]
input: a = [-1]
output: [0] (একা, ডানে কেউ নেই)
input: a = [-1, -1]
output: [0, 0] (equal, strictly ছোট নয়)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো একটা দৌড় শেষে finishers এক এক করে ভেতরে ঢুকছে, সবার গায়ে bib-number। শেষ থেকে দেখলে — প্রতিটা নতুন finisher-এর জন্য তুমি জানতে চাও "এর পরে যারা এসেছে (মানে board-এ ইতিমধ্যে আছে), তাদের কয়জনের bib এর চেয়ে ছোট"। প্রতিবার পুরো board না গুনে, bib-number অনুযায়ী একটা tally রাখো; নতুন bib-এ শুধু তার নিচের অংশটা যোগ করো।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা **BIT-over-values আর sorting**-এর উপর দাঁড়িয়ে। #10-এ তুমি মোট inversion গুনেছিলে; এটা ঠিক তার per-element রূপ — প্রতিটা element আলাদা করে জানতে চায় তার ডানে কয়টা ছোট। BIT এখানে আবার একটা frequency table over values।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic: **array ডান থেকে বাঁয়ে process করো; প্রতিটা value frequency table-এ tick দেওয়ার আগে জিজ্ঞেস করো "এ পর্যন্ত (অর্থাৎ আমার ডানে) কয়টা value আমার চেয়ে ছোট দেখা হয়েছে"**। সেই answer-টাই `counts[i]`। ডান-থেকে-বাঁ order নিশ্চিত করে BIT-এ শুধু "ডানের" element-রাই আছে।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **Fenwick tree (BIT) value-দের rank-এ indexed**। Value 10^4 পর্যন্ত বড় (আর negative) হতে পারে, তাই আগে **coordinate compression** (value → rank)।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
"আমার চেয়ে ছোট কয়টা ইতিমধ্যে দেখেছি" = `prefix_sum(rank - 1)` over a frequency table। BIT এই prefix-count আর point-increment দুটোই O(log n)-এ দেয়। n element-এ মোট O(n log n) — segment tree-ও পারত, কিন্তু BIT ছোট আর দ্রুত ([../fenwick-tree.md](../fenwick-tree.md) section 8-9 দেখো)।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
সরল চিন্তা: প্রতি `i`-র জন্য ডানদিকের সব element ঘুরে ছোট গোনা।
```text
for i in range(n):
counts[i] = 0
for j in range(i+1, n):
if a[j] < a[i]:
counts[i] += 1
```
নির্ভুল, এটাই reference।
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
দুই nested loop = O(n^2)। n = 10^5 হলে 10^10 — TLE। BIT-over-values প্রতি element-এ একটা prefix-count + একটা update দিয়ে পুরোটা **O(n log n)**-এ নামায়।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **"ডানে কয়টা ছোট" = ডান-থেকে-বাঁ গেলে "এ পর্যন্ত দেখা value-গুলোর মধ্যে কয়টা ছোট"**। Order উল্টে দিলে ভবিষ্যৎ (ডান) অতীত হয়ে যায়, আর প্রশ্নটা একটা frequency-table prefix-count-এ পরিণত হয়।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
Coordinate compression করে value → rank। তারপর `i = n-1` থেকে `0` পর্যন্ত: `counts[i] = prefix_sum(rank[i] - 1)` (strictly ছোট), তারপর `add(rank[i], 1)`। `rank - 1` strict ছোট নিশ্চিত করে (equal value বাদ)। ডান-থেকে-বাঁ order মানে BIT-এ শুধু ডানের element।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** per-element "ডানে কয়টা ছোট" প্রশ্নকে একটা *running frequency table*-এর উপর prefix-count-এ অনুবাদ করো, আর array উল্টো দিকে হাঁটো। এই reverse-sweep + BIT-frequency জোড়া #14, #16-এও ফিরে আসবে।
### ছবিতে বোঝা {#7-visual-explanation}
```text
a = [5, 2, 6, 1] compressed rank (1->1, 2->2, 5->3, 6->4):
a: 5 2 6 1
rank: 3 2 4 1
ডান -> বাঁ, frequency BIT-এ tick দিতে দিতে:
a[3]=1 (rank1): prefix_sum(0) = 0 -> counts[3]=0; add(1,1)
a[2]=6 (rank4): prefix_sum(3) = 1 -> counts[2]=1; add(4,1) (শুধু 1 marked)
a[1]=2 (rank2): prefix_sum(1) = 1 -> counts[1]=1; add(2,1) (শুধু 1)
a[0]=5 (rank3): prefix_sum(2) = 2 -> counts[0]=2; add(3,1) (1, 2)
counts = [2, 1, 1, 0]
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`a = [5, 2, 6, 1]`, rank `{1:1, 2:2, 5:3, 6:4}`, BIT খালি। `i = 3 → 0`:
1. i=3, a=1 (r=1): `prefix_sum(0)=0` → counts[3]=0; `add(1,1)`।
2. i=2, a=6 (r=4): `prefix_sum(3)=1` (শুধু r1) → counts[2]=1; `add(4,1)`।
3. i=1, a=2 (r=2): `prefix_sum(1)=1` (শুধু r1) → counts[1]=1; `add(2,1)`।
4. i=0, a=5 (r=3): `prefix_sum(2)=2` (r1, r2) → counts[0]=2; `add(3,1)`।
5. counts = `[2, 1, 1, 0]`। ✓
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
class Fenwick:
"""1-indexed BIT, value-দের frequency table হিসেবে। index মানে VALUE-র rank,
position নয়। add(i, 1): value-rank i একবার দেখলাম; prefix_sum(i): rank 1..i-র
মোট গোনা। দুটোই O(log n)।"""
def __init__(self, n):
self.n = n
self.tree = [0] * (n + 1)
def add(self, i, delta):
while i <= self.n:
self.tree[i] += delta
i += i & (-i)
def prefix_sum(self, i):
s = 0
while i > 0:
s += self.tree[i]
i -= i & (-i)
return s
def count_smaller(a):
n = len(a)
if n == 0:
return []
# coordinate compression: value -> 1-indexed rank
order = sorted(set(a))
rank = {v: idx + 1 for idx, v in enumerate(order)}
bit = Fenwick(len(order))
counts = [0] * n
for i in range(n - 1, -1, -1): # ডান -> বাঁ
r = rank[a[i]]
counts[i] = bit.prefix_sum(r - 1) # ডানে দেখা, আমার চেয়ে ছোট কয়টা
bit.add(r, 1) # নিজেকে frequency table-এ tick
return counts
def brute(a):
# obviously-correct O(n^2) reference
n = len(a)
res = [0] * n
for i in range(n):
for j in range(i + 1, n):
if a[j] < a[i]:
res[i] += 1
return res
# ---- tests ----
assert count_smaller([5, 2, 6, 1]) == [2, 1, 1, 0]
assert count_smaller([-1]) == [0]
assert count_smaller([-1, -1]) == [0, 0] # equal: strictly ছোট নয়
assert count_smaller([]) == [] # empty
assert count_smaller([1, 2, 3, 4]) == [0, 0, 0, 0] # increasing: ডানে কিছু ছোট নেই
assert count_smaller([4, 3, 2, 1]) == [3, 2, 1, 0] # decreasing: সব ডানেরটা ছোট
# BIT version সবসময় brute-এর সাথে একমত (duplicate, negative-সহ)
import random
for _ in range(400):
arr = [random.randint(-6, 6) for _ in range(random.randint(0, 15))]
assert count_smaller(arr) == brute(arr)
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `Fenwick` — standard BIT, এখানে value-দের frequency table; index = rank।
- `order`/`rank` — coordinate compression, value → `1..k`; বড়/negative value সামলায়।
- `count_smaller` — `i` কমার দিকে (ডান → বাঁ) হাঁটে; `prefix_sum(r-1)` দেয় ডানে-দেখা ছোট value-র সংখ্যা।
- `r - 1` — strictly ছোট চাই বলে নিজের সমান value বাদ।
- `brute` — O(n^2), নির্ভুল reference।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`[5,2,6,1]`-এ ডান-থেকে-বাঁ হেঁটে BIT version দেয় `[2,1,1,0]` (section 14)। তারপর 400-টা random array-তে — duplicate আর negative-সহ — brute-এর সাথে হুবহু মেলে। equal value (`[-1,-1]`) strictly ছোট নয় বলে `[0,0]`। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n log n):** প্রতি element-এ একটা `prefix_sum` + একটা `add`, প্রতিটা O(log n); compression-এর sort O(n log n)।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(n):** BIT array + rank map + output array।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- BIT-এ index হিসেবে position নেওয়া — index মানে VALUE-র rank, এটাই মূল মোচড়।
- বাঁ-থেকে-ডান হাঁটা — তখন "ডানে কয়টা ছোট"-এর বদলে "বাঁয়ে কয়টা ছোট" পাও; reverse sweep জরুরি।
- `prefix_sum(r)` লেখা যেখানে `prefix_sum(r - 1)` দরকার — equal value-ও গোনা হয়ে strict ভাঙে।
- Coordinate compression বাদ — বড়/negative value-তে BIT index crash বা বিশাল array।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: BIT-over-values ([../fenwick-tree.md](../fenwick-tree.md) section 9) + sorting (compression)। সরাসরি বড় ভাই #10 (count inversions) — সেখানে মোট গোনা, এখানে per-element।
### পরের অনুশীলন {#22-similar-harder-problems}
- Reverse Pairs (`a[i] > 2*a[j]` শর্ত, একই reverse-sweep) —