题解 | 计算数组的小和

package main

import "fmt"

var (
	res int64
)

func main() {
	res = 0
	var (
		n int
	)
	fmt.Scan(&n)
	arr := make([]int, n)
	
	for i := 0; i < n; i++ {
		fmt.Scan(&arr[i])
	}
	smallSum(arr, 0, n-1)
	fmt.Println(res)
}

func smallSum(arr []int, l int, r int) {
	if r == l {
		return
	}
	mid := (r-l)/2 + l
	smallSum(arr, l, mid)
	smallSum(arr, mid+1, r)
	merge(arr, l, mid, r)
}
func merge(arr []int, l int, mid int, r int) {
	help := make([]int, r-l+1)
	i := l
	j := mid + 1
	idx := 0

	for i <= mid && j <= r {
		if arr[i] <= arr[j] {
			res += int64((r - j + 1) * arr[i])
			help[idx] = arr[i]
			i++
		} else {
			help[idx] = arr[j]
			j++
		}
		idx++
	}
	for i <= mid {
		help[idx] = arr[i]
		i++
		idx++
	}
	for j <= r {
		help[idx] = arr[j]
		j++
		idx++
	}
	for i := 0; i < len(help); i++ {
		arr[i+l] = help[i]
	}
}