Implement the Log Trick to find distinct subarray operation values
The 'log trick' is an optimization for problems requiring the calculation of bitwise OR, AND, or GCD across all subarrays. Because these operations are monotonic (the result only changes a logarithmic number of times as the subarray grows), you can maintain a compressed list of distinct values and their corresponding boundaries instead of iterating through all $O(n^2)$ subarrays.
This is particularly useful for counting how many subarrays result in a specific value or finding all unique values produced by these operations.
// Generic implementation to count occurrences of each distinct value
// produced by a monotonic operation (like OR, AND, GCD) across all subarrays.
func logTrick(nums []int, op func(x, y int) int) map[int]int {
res := map[int]int{}
type pair struct{ l, r, v int }
dp := []pair{}
for pos, cur := range nums {
// Update existing subarray results with the current element
for i := range dp {
dp[i].v = op(dp[i].v, cur)
}
// Add the single-element subarray starting and ending at current position
dp = append(dp, pair{pos, pos + 1, cur})
// Merge adjacent subarrays that now have the same operation value
ptr := 0
for _, v := range dp[1:] {
if dp[ptr].v != v.v {
ptr += 1
dp[ptr] = v
} else {
dp[ptr].r = v.r
}
}
dp = dp[:ptr+1]
// Accumulate the count of subarrays for each distinct value
for _, v := range dp {
res[v.v] += v.r - v.l
}
}
return res
}
// Example operation functions to use with logTrick
func and(a, b int) int { return a & b }
func or(a, b int) int { return a | b }
func gcd(a, b int) int {
for a != 0 {
a, b = b%a, a
}
return b
}