Sum over subsets transform
Your task
You are given an array a of length 2^k, indexed by bitmasks 0..2^k-1. Compute the sum-over-subsets transform: return a new array f where f[mask] equals the sum of a[sub] over every submask sub of mask (including mask itself and 0). Lengths up to 2^16 must finish quickly.
Examples
sum_over_submasks(a: list[int]) -> list[int]Example 1
Input
sum_over_submasks([1, 2, 3, 4])Output
[1, 3, 4, 10]