โปรแกรมนับจำนวน Shift ใน Insertion Sort ด้วย Fenwick Tree ใน Python

ให้ Array หาจำนวน Shift รวมเมื่อทำ Insertion Sort (O(n log n) ด้วย BIT)

ตัวอย่าง: [4,5,3,1,2] → 8

ขั้นตอน (Fenwick Tree / BIT)

1. BIT Size 1,000,001 สำหรับนับ Frequency
2. วน item ใน Array:
   • Query BIT: ผลรวม Index ≤ item = จำนวนที่ ≤ item ก่อนหน้า
   • Inversion += (Processed - Query)
   • Update BIT: เพิ่ม Frequency ที่ item
3. Total Shifts = n*(n-1)/2 - Inversion (หรือนับ Inversion ตรง)

ตัวอย่างโค้ด

def solve(input_arr):
    length = len(input_arr)
    temp_arr = [0] * 1000001
    ans = 0
    for item in input_arr:
        val = item
        while val > 0:
            ans += temp_arr[val]
            val -= val & -val
        val = item
        while val <= 1000000:
            temp_arr[val] += 1
            val += val & -val
    ans = length * (length - 1) // 2 - ans
    return ans

print(solve([4, 5, 3, 1, 2]))  # Output: 8

อินพุต

[4, 5, 3, 1, 2]

เอาต์พุต

8