Submask Sum Queries
Intuit● HardINTERNOAProblem statement
You are given a nonnegative bit count n, an integer array values of length 2^n, and an array of query masks queries.
A mask s is a submask of m when every set bit of s is also set in m. For each query mask m, return the sum of values[s] over every submask s of m. Return answers in the same order as the queries.
Function
sumSubmaskValues(n: int, values: long[], queries: int[]) → long[]Examples
Example 1
n = 2values = [1,2,3,4]queries = [3,1]return = [10,3]Every mask from 0 through 3 is a submask of 3, so the first sum is 1 + 2 + 3 + 4 = 10. The submasks of 1 are 0 and 1, producing 1 + 2 = 3.
Example 2
n = 1values = [-2,5]queries = [0,1]return = [-2,3]Mask 0 has only itself as a submask, so the first result is -2. Mask 1 has submasks 0 and 1, producing -2 + 5 = 3.
Constraints
0 ≤ n ≤ 12andvalues.length = 2^n.-10^9 ≤ values[i] ≤ 10^9.1 ≤ queries.length ≤ 1000and every query is a valid mask in[0, 2^n - 1].- Every answer fits in a signed 64-bit integer.