Small Sum Problem (Merge Sort Counting)
用归并分治在 O(n log n) 内计算数组小和。
#resource / algorithm
#type / howto
#status / growing
#algo / divide-and-conquer
#algo / sort
[!info] related notes 算法面试题型 MOC 分治
Small Sum Problem
问题定义（常见版本）：
- 对数组中每个位置 j，统计它左侧所有
<= arr[j]的数之和；把所有位置的这个和累加，得到“小和”。
分治视角
在 merge sort 的 merge 阶段：
- 左半有序、右半有序。
- 对右侧每个元素
arr[j]，可以用双指针维护左侧所有<= arr[j]的前缀和，把贡献一次性加进去。
整体复杂度：O(n log n)。
Java Template
import java.util.*;
public class SmallSum {
static int[] arr;
static int[] help;
public static long smallSum(int[] nums) {
if (nums == null || nums.length < 2) return 0;
arr = nums;
help = new int[nums.length];
return solve(0, nums.length - 1);
}
static long solve(int l, int r) {
if (l == r) return 0;
int m = l + ((r - l) >> 1);
return solve(l, m) + solve(m + 1, r) + mergeAndCount(l, m, r);
}
// returns small-sum contribution across left/right and merges sorted
static long mergeAndCount(int l, int m, int r) {
long ans = 0;
// count cross contribution
int i = l;
long prefixSum = 0;
for (int j = m + 1; j <= r; j++) {
while (i <= m && arr[i] <= arr[j]) {
prefixSum += arr[i++];
}
ans += prefixSum;
}
// standard merge
int p1 = l, p2 = m + 1, k = l;
while (p1 <= m && p2 <= r) {
help[k++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
}
while (p1 <= m) help[k++] = arr[p1++];
while (p2 <= r) help[k++] = arr[p2++];
for (int x = l; x <= r; x++) arr[x] = help[x];
return ans;
}
}