Skip to content

010 — Count Inversions Two Ways

Source

  • Original source: self-exercise (classic counting problem)
  • Platform: self-exercise — কোনো single judge নেই, ইচ্ছে করেই দুটো পদ্ধতি পাশাপাশি
  • Topic: segment tree and fenwick tree
  • Difficulty: Medium
  • Pattern: counting with BIT (merge sort vs Fenwick tree, পাশাপাশি)
  • Basic idea inherited from: sorting, BIT over values

1. Problem in simple words

একটা array a দেওয়া আছে। একটা inversion হলো এমন একজোড়া index (i, j) যেখানে i < j কিন্তু a[i] > a[j] — মানে দুটো element ভুল ক্রমে বসে আছে। তোমার কাজ: মোট কতগুলো inversion আছে গোনা। এটা দুইভাবে করো — প্রথমে merge sort দিয়ে, তারপর Fenwick tree দিয়ে — আর দুই উত্তর মিলিয়ে দেখো।

a = [2, 3, 8, 6, 1]

inversions: (8,6), (2,1), (3,1), (8,1), (6,1)  ->  মোট 5

2. Which basic idea does this inherit from?

এটা sorting আর BIT-over-values-এর উপর দাঁড়িয়ে। Inversion মানে কতটা array sort থেকে দূরে — তাই sorting algorithm-গুলোই এটা গোনার সবচেয়ে স্বাভাবিক জায়গা। আর Fenwick পথে BIT-টা index মানে position নয়, value — ঠিক যেমন ../fenwick-tree.md section 9-এ frequency table।

3. What is the hidden math or logic?

লুকানো logic: প্রতিটা element ডানদিকে কতগুলো ছোট element ফেলে গেছে, সব যোগ করলেই মোট inversion। অথবা সমতুল্যভাবে — বাঁ দিক থেকে এগোলে — নতুন element-এর আগে কতগুলো বড় element ইতিমধ্যে এসেছে। দুটো গোনার পদ্ধতিই এই একই যোগফলে পৌঁছায়, শুধু রাস্তা আলাদা।

4. Which data structure is needed?

দুটো বিকল্প: merge sort (count করতে করতে merge), বা একটা Fenwick tree (BIT) যেটা value-দের frequency জমায়। BIT পথে value বড় হতে পারে, তাই আগে coordinate compression (value → rank)।

5. Why this data structure fits

Merge sort প্রতিটা merge step-এ এক ঝটকায় গুনে ফেলতে পারে কতগুলো cross-pair inverted — কারণ দুই অর্ধেক sorted। Fenwick এদিকে "এ পর্যন্ত কয়টা value ≤ x দেখেছি" — এই prefix-count query-টা O(log n)-এ দেয়, যা inversion গোনার ঠিক হাতিয়ার।

6. Real-life analogy

ভাবো একদল ছাত্র এলোমেলো লাইনে দাঁড়িয়ে, সবার গায়ে roll number লেখা। একজন শিক্ষক চান লাইনটা কত "অগোছালো" মাপতে — প্রতিবার যখন সামনের একজনের roll পেছনের একজনের চেয়ে বড়, সেটা একটা ভুল জুড়ি। মোট ভুল জুড়ির সংখ্যাই inversion — পুরো লাইনকে ঠিক করতে অন্তত কতগুলো অদলবদল লাগবে তার মাপ।

7. Visual explanation

a = [2, 3, 8, 6, 1]   (index:  0  1  2  3  4)

প্রতিটা element-এর ডানে কয়টা ছোট element আছে গোনো:
  a[0]=2 -> ডানে ছোট: {1}            -> 1
  a[1]=3 -> ডানে ছোট: {1}            -> 1
  a[2]=8 -> ডানে ছোট: {6, 1}         -> 2
  a[3]=6 -> ডানে ছোট: {1}            -> 1
  a[4]=1 -> ডানে ছোট: {}             -> 0
                                  total = 5

Fenwick পথ (ডান -> বাঁ, value-দের frequency table-এ tick দিতে দিতে):
  দেখি 1 -> "এর চেয়ে ছোট কয়টা দেখেছি?" = 0,  then mark 1
  দেখি 6 -> ছোট কয়টা? = 1 (only 1),        then mark 6
  দেখি 8 -> ছোট কয়টা? = 2 (1, 6),          then mark 8
  দেখি 3 -> ছোট কয়টা? = 1 (only 1),        then mark 3
  দেখি 2 -> ছোট কয়টা? = 1 (only 1),        then mark 2
                                  total = 5

8. Example input and output

input:  a = [2, 3, 8, 6, 1]
output: 5

input:  a = [1, 2, 3, 4]
output: 0            (already sorted, no inversions)

input:  a = [4, 3, 2, 1]
output: 6            (fully reversed: n*(n-1)/2 = 4*3/2)

9. Brute force thinking

সবচেয়ে সরল চিন্তা: প্রতিজোড়া (i, j) দেখো, i < j আর a[i] > a[j] হলে গোনো।

for i in range(n):
    for j in range(i+1, n):
        if a[i] > a[j]:
            count += 1

ছোট array-তে নিখুঁত, আর এটাই আমাদের brute-force reference।

10. Why brute force is slow

দুই nested loop মানে O(n^2) জোড়া। n = 100,000 হলে প্রায় 10^10 operation — judge time limit-এ ফেল। Merge sort আর Fenwick দুটোই এটাকে O(n log n)-এ নামিয়ে আনে।

11. Key observation

মূল observation: inversion local নয়, কিন্তু গোছানো যায়। Merge sort-এ যখন ডান অর্ধেকের একটা element বাঁ অর্ধেকের কোনো element-এর আগে বসে, তখন বাঁ অর্ধেকের বাকি সব element-এর সাথে সে inverted — এক ঝটকায় গোনা যায়। Fenwick-এ "ডানে কয়টা ছোট" = "frequency table-এ আমার rank-এর নিচে কয়টা tick"।

12. Optimized intuition

Merge sort: দুই sorted অর্ধেক merge করার সময়, ডান থেকে একটা ছোট element তুললে বাঁ অর্ধেকে যত element বাকি, ততগুলো inversion যোগ হয়। Fenwick: array ডান থেকে বাঁয়ে ঘুরে, প্রতিটা value-র rank-এ add(rank, 1); আগে prefix_sum(rank - 1) জিজ্ঞেস করলেই পাও "এর চেয়ে কম value কয়টা ইতিমধ্যে (ডানদিকে) দেখা হয়েছে"।

13. Thinking tweak

মোচড়: জোড়া গোনাকে "প্রতিটা element ডানদিকে কয়টা ছোট ফেলে গেল" — এই per-element প্রশ্নে ভাঙো। তখন BIT-টা একটা frequency counter হয়ে যায়, summer নয়। এই দৃষ্টিভঙ্গিই #13, #14, #16-এর পথ খুলে দেয়।

14. Step-by-step dry run

a = [2, 3, 8, 6, 1], Fenwick পথ (compressed rank: 1→1, 2→2, 3→3, 6→4, 8→5)। ডান থেকে বাঁ:

  1. value 1 (rank 1): prefix_sum(0) = 0 → +0; add(1, 1)।
  2. value 6 (rank 4): prefix_sum(3) = 1 (শুধু rank 1 marked) → +1; add(4, 1)।
  3. value 8 (rank 5): prefix_sum(4) = 2 (rank 1, 4) → +2; add(5, 1)।
  4. value 3 (rank 3): prefix_sum(2) = 1 (শুধু rank 1) → +1; add(3, 1)।
  5. value 2 (rank 2): prefix_sum(1) = 1 (শুধু rank 1) → +1; add(2, 1)।
  6. মোট = 0 + 1 + 2 + 1 + 1 = 5। ✓

15. Python solution

class Fenwick:
    """1-indexed Binary Indexed Tree। এখানে index মানে একটা VALUE-র rank,
    position নয়। add(i, delta): element i-তে delta যোগ; prefix_sum(i):
    1..i-র sum। দুটোই 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_inversions_fenwick(a):
    # coordinate compression: value -> 1-indexed rank
    order = sorted(set(a))
    rank = {v: idx + 1 for idx, v in enumerate(order)}
    bit = Fenwick(len(order))
    inv = 0
    for x in reversed(a):                 # ডান থেকে বাঁ
        r = rank[x]
        inv += bit.prefix_sum(r - 1)      # ইতিমধ্যে দেখা, আমার চেয়ে ছোট কয়টা
        bit.add(r, 1)                     # নিজেকে frequency table-এ tick দাও
    return inv


def count_inversions_merge(a):
    # merge sort, merge-এর সময় cross-inversion গোনে
    def sort_count(arr):
        if len(arr) <= 1:
            return arr, 0
        mid = len(arr) // 2
        left, cl = sort_count(arr[:mid])
        right, cr = sort_count(arr[mid:])
        merged, cm = [], 0
        i = j = 0
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                merged.append(left[i])
                i += 1
            else:                          # right[j] left-এর বাকি সবার আগে বসছে
                merged.append(right[j])
                j += 1
                cm += len(left) - i        # বাঁয়ে যত বাকি, ততগুলো inversion
        merged.extend(left[i:])
        merged.extend(right[j:])
        return merged, cl + cr + cm

    return sort_count(a)[1]


def brute(a):
    # obviously-correct O(n^2) reference
    inv = 0
    for i in range(len(a)):
        for j in range(i + 1, len(a)):
            if a[i] > a[j]:
                inv += 1
    return inv


# ---- tests ----
a = [2, 3, 8, 6, 1]
assert count_inversions_fenwick(a) == 5
assert count_inversions_merge(a) == 5
assert brute(a) == 5

assert count_inversions_fenwick([1, 2, 3, 4]) == 0     # already sorted
assert count_inversions_merge([4, 3, 2, 1]) == 6       # fully reversed
assert count_inversions_fenwick([]) == 0               # empty
assert count_inversions_fenwick([7]) == 0              # single element

# তিন পদ্ধতি random array-তে সবসময় একমত (with duplicates too)
import random
for _ in range(300):
    arr = [random.randint(0, 9) for _ in range(random.randint(0, 12))]
    expected = brute(arr)
    assert count_inversions_fenwick(arr) == expected
    assert count_inversions_merge(arr) == expected

print("সব test pass!")

16. Line-by-line code explanation

  • Fenwick — section 5-এর standard BIT, কিন্তু index এখানে VALUE-র rank।
  • order/rank — coordinate compression: value-গুলোকে 1..k rank-এ চেপে দেয়, যাতে BIT ছোট থাকে এমনকি value 10^9 হলেও।
  • count_inversions_fenwick — array reverse করে ঘোরে; prefix_sum(r-1) দেয় ইতিমধ্যে-দেখা ছোট value-র সংখ্যা।
  • count_inversions_merge — merge step-এ len(left) - i যোগ করে: ডান element বসলে বাঁয়ের বাকি সবার সাথে inverted।
  • brute — O(n^2), নির্ভুল, fast দুটোকে যাচাই করতে।

17. Output walkthrough

[2, 3, 8, 6, 1]-এর জন্য Fenwick দেয় 5 (section 14-এর trace), merge sort-ও দেয় 5, brute-ও 5। তারপর 300-টা random array-তে — duplicate-সহ — তিন পদ্ধতিই সবসময় একমত। শেষে print: সব test pass!।

18. Time complexity

দুই পদ্ধতিই O(n log n): merge sort-এর recursion O(n log n), Fenwick-এ প্রতিটা element-এ একটা prefix_sum + একটা add, প্রতিটা O(log n)। Compression-এর sort-ও O(n log n)।

19. Space complexity

O(n): Fenwick পথে BIT array + rank map; merge sort-এ recursion + temporary merged list।

20. Common mistakes

  • Fenwick-এ index হিসেবে position নেওয়া (value/rank-এর বদলে) — এটাই #1 ভুল; BIT-টা value-দের frequency table।
  • Coordinate compression ভুলে যাওয়া — value বড় হলে BIT array অসম্ভব বড় (বা negative value-তে crash)।
  • Merge step-এ <= না দিয়ে < দেওয়া — equal element-কে inversion হিসেবে গুনে ভুল overcount।
  • prefix_sum(r) লেখা যেখানে prefix_sum(r - 1) দরকার — তাহলে নিজের সমান value-ও গোনা হয়।

21. Which basic problem this inherits from

ভিত্তি: sorting (merge sort-এর divide and conquer) + BIT-over-values (../fenwick-tree.md section 9)। আগের ভিত্তি: ../../01-math-based-programming-fundamentals/-এর bit manipulation, যেখান থেকে i & (-i) এসেছে।

22. Similar harder problems

23. Pattern learned

Counting with BIT: জোড়া-গোনাকে per-element "ডানে কয়টা ছোট" প্রশ্নে ভাঙা, আর সেটা frequency table হিসেবে BIT দিয়ে O(log n)-এ উত্তর দেওয়া। Merge sort এর সমান্তরাল রাস্তা — একই answer, ভিন্ন lens।

24. Final summary

ভবিষ্যতের আমাকে: inversion = "প্রতি element ডানদিকে কয়টা ছোট ফেলে গেল"-এর যোগফল। দুটো পথ আছে — merge-এর সময় cross-pair গোনা, বা value-দের frequency BIT-এ ডান-থেকে-বাঁ ঘুরে prefix-count। BIT-এ index মানে VALUE — এই এক কথাটা মাথায় গেঁথে গেলে #13, #14, #16 স্রেফ এই idea-র variation।

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