Prefix Sum (前綴和)

for i in range(len(cnt)):
    prefix[i + 1] = prefix[i] + cnt[i]

cnt = [1, 0, 1, 1, 1]

# Step 1: allocate size n+1, fill with 0
#   the leading prefix[0] = 0 is the "empty sum" sentinel
#   -> lets sum(0, r) work without a special case
prefix = [0] * (len(cnt) + 1)
# prefix = [0, 0, 0, 0, 0, 0]

# Step 2: each prefix[i+1] = running total up to (and including) cnt[i]
for i in range(len(cnt)):
    prefix[i + 1] = prefix[i] + cnt[i]

# prefix = [0, 1, 1, 2, 3, 4]

cnt:        [ 1,  0,  1,  1,  1 ]
index i:      0   1   2   3   4

prefix[0] = 0                 ← sentinel (empty prefix)
prefix[1] = prefix[0] + cnt[0] = 0 + 1 = 1
prefix[2] = prefix[1] + cnt[1] = 1 + 0 = 1
prefix[3] = prefix[2] + cnt[2] = 1 + 1 = 2
prefix[4] = prefix[3] + cnt[3] = 2 + 1 = 3
prefix[5] = prefix[4] + cnt[4] = 3 + 1 = 4

prefix = [0, 1, 1, 2, 3, 4]
          ↑                 ↑
       empty sum        sum of ALL cnt

from itertools import accumulate
prefix = list(accumulate(cnt, initial=0))   # [0, 1, 1, 2, 3, 4]

Given nums:    [ a,  b,  c,  d,  e ]
Index:           0   1   2   3   4

Build prefix array (size n+1, prefix[0] = 0):

prefix[0] = 0
prefix[1] = a
prefix[2] = a + b
prefix[3] = a + b + c
prefix[4] = a + b + c + d
prefix[5] = a + b + c + d + e

Visual:

prefix:  0 |  a  | a+b | a+b+c | a+b+c+d | a+b+c+d+e |
index:   0    1      2      3        4          5

To get sum(l=1, r=3) = nums[1] + nums[2] + nums[3] = b + c + d:

prefix[r+1] = prefix[4] = a + b + c + d
prefix[l]   = prefix[1] = a
                           ─────────────
prefix[4] - prefix[1]   =     b + c + d  ✓

Visually (what gets cancelled out):

prefix[4]:  [ a | b | c | d ]
prefix[1]:  [ a ]
            ─────────────────
difference:     [ b | c | d ]   ← this is sum(1, 3)

sum(0, 2) = prefix[3] - prefix[0]
          = (a + b + c) - 0
          = a + b + c  ✓

nums = [-2, 0, 3, -5, 2, -1]

Step 1: Build prefix array
prefix = [0, -2, -2, 1, -4, -2, -3]
              ↑    ↑  ↑   ↑   ↑   ↑
              -2  -2+0 ...        sum of all

Step 2: Query
sumRange(0, 2) = prefix[3] - prefix[0] = 1 - 0 = 1       ✓  (-2+0+3)
sumRange(2, 5) = prefix[6] - prefix[2] = -3 - (-2) = -1  ✓  (3-5+2-1)
sumRange(0, 5) = prefix[6] - prefix[0] = -3 - 0 = -3     ✓  (-2+0+3-5+2-1)

def prefix_sum_solve(nums, target):
    """
    Universal prefix sum template for most problems
    """
    # Step 1: Initialize prefix sum and result
    prefix_sum = 0
    result = 0
    
    # Step 2: HashMap for storing prefix sums (if needed)
    prefix_map = {0: 1}  # Handle subarrays starting from index 0
    
    # Step 3: Iterate through array
    for num in nums:
        # Update prefix sum
        prefix_sum += num
        
        # Check condition based on problem type
        if prefix_sum - target in prefix_map:
            result += prefix_map[prefix_sum - target]
        
        # Update map
        prefix_map[prefix_sum] = prefix_map.get(prefix_sum, 0) + 1
    
    return result

class PrefixSum:
    def __init__(self, nums):
        """Build prefix sum array for range queries"""
        self.prefix = [0] * (len(nums) + 1)
        for i in range(len(nums)):
            self.prefix[i + 1] = self.prefix[i] + nums[i]
    
    def range_sum(self, left, right):
        """Get sum of elements from index left to right (inclusive)"""
        return self.prefix[right + 1] - self.prefix[left]

// Java implementation
class PrefixSum {
    private int[] prefix;
    
    public PrefixSum(int[] nums) {
        prefix = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
    }
    
    public int rangeSum(int left, int right) {
        return prefix[right + 1] - prefix[left];
    }
}

def subarray_sum_equals_k(nums, k):
    """Count subarrays with sum equal to k"""
    count = 0
    prefix_sum = 0
    prefix_map = {0: 1}  # Important: initialize with {0: 1}
    
    for num in nums:
        prefix_sum += num
        
        # Check if (prefix_sum - k) exists
        if prefix_sum - k in prefix_map:
            count += prefix_map[prefix_sum - k]
        
        # Update map
        prefix_map[prefix_sum] = prefix_map.get(prefix_sum, 0) + 1
    
    return count

// Java implementation
public int subarraySum(int[] nums, int k) {
    int count = 0, prefixSum = 0;
    Map<Integer, Integer> map = new HashMap<>();
    map.put(0, 1);  // Handle subarrays starting from index 0
    
    for (int num : nums) {
        prefixSum += num;
        
        if (map.containsKey(prefixSum - k)) {
            count += map.get(prefixSum - k);
        }
        
        map.put(prefixSum, map.getOrDefault(prefixSum, 0) + 1);
    }
    
    return count;
}

Let prefix[i] = sum of nums[0..i]

A subarray sum nums[j+1..i] is divisible by k:
  (prefix[i] - prefix[j]) % k == 0

This implies:
  prefix[i] % k == prefix[j] % k

So if we see the SAME remainder again at index i vs a previous index j,
the subarray nums[j+1..i] has sum divisible by k.

map stores: { remainder -> earliest index }

If the current remainder already exists in the map
AND the distance (i - map[remainder]) >= 2, we found a valid subarray.

def subarray_divisible_by_k(nums, k):
    """Count subarrays with sum divisible by k"""
    count = 0
    prefix_sum = 0
    remainder_map = {0: 1}  # remainder -> count
    
    for num in nums:
        prefix_sum += num
        remainder = prefix_sum % k
        
        # Handle negative remainders
        if remainder < 0:
            remainder += k
        
        if remainder in remainder_map:
            count += remainder_map[remainder]
        
        remainder_map[remainder] = remainder_map.get(remainder, 0) + 1
    
    return count

def range_addition(length, updates):
    """Apply multiple range additions efficiently"""
    # Step 1: Create difference array
    diff = [0] * (length + 1)
    
    # Step 2: Apply range updates to difference array
    for start, end, val in updates:
        diff[start] += val
        diff[end + 1] -= val
    
    # Step 3: Compute prefix sum to get final result
    result = []
    current_sum = 0
    for i in range(length):
        current_sum += diff[i]
        result.append(current_sum)
    
    return result

class NumMatrix:
    def __init__(self, matrix):
        """Build 2D prefix sum matrix"""
        if not matrix or not matrix[0]:
            return
        
        m, n = len(matrix), len(matrix[0])
        self.prefix = [[0] * (n + 1) for _ in range(m + 1)]
        
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                self.prefix[i][j] = (matrix[i-1][j-1] + 
                                   self.prefix[i-1][j] + 
                                   self.prefix[i][j-1] - 
                                   self.prefix[i-1][j-1])
    
    def sumRegion(self, row1, col1, row2, col2):
        """Calculate sum of rectangle from (row1,col1) to (row2,col2)"""
        return (self.prefix[row2+1][col2+1] - 
                self.prefix[row1][col2+1] - 
                self.prefix[row2+1][col1] + 
                self.prefix[row1][col1])

def count_nice_subarrays(nums, k):
    """Count subarrays with exactly k odd numbers"""
    # Transform: odd -> 1, even -> 0
    transformed = [1 if x % 2 == 1 else 0 for x in nums]

    # Now it's subarray sum equals k problem
    count = 0
    prefix_sum = 0
    prefix_map = {0: 1}

    for val in transformed:
        prefix_sum += val

        if prefix_sum - k in prefix_map:
            count += prefix_map[prefix_sum - k]

        prefix_map[prefix_sum] = prefix_map.get(prefix_sum, 0) + 1

    return count

indices = [i_0, i_1, i_2, ..., i_{m-1}]   the sorted indices of ONE value
m       = len(indices)

For the element at RANK k inside that group:
  idx       = indices[k]      its position in the ORIGINAL array
  left_cnt  = k               how many equal values sit before it
  right_cnt = m - 1 - k       how many sit after it

Prefix sum over the group (size m+1, leading sentinel):
  prefix[0]     = 0                                  the empty sum
  prefix[k]     = i_0 + i_1 + ... + i_{k-1}          first k     → everything LEFT of rank k
  prefix[k + 1] = i_0 + i_1 + ... + i_k              first k + 1 → the left part, plus idx itself
  prefix[m]     = i_0 + i_1 + ... + i_{m-1}          the whole group

prefixSum[i] = nums[0] + nums[1] + ... + nums[i-1]

  -> so, when we say prefixSum[i],
     we are summing the values in [0, i-1]   ← i is EXCLUSIVE, i itself is NOT in the sum

Applied to a group's indices:

  -> i_0 + i_1 + ... + i_{k-1}          is   prefix[k]
     (everything strictly LEFT of rank k)          upper end k is excluded, so idx is out ✓

  -> i_{k+1} + i_{k+2} + ... + i_{m-1}  is   prefix[m] - prefix[k + 1]
     (everything strictly RIGHT of rank k)         whole group, minus the first k+1 (which ends AT idx)

rank k:      0   1   2    3
indices:     2   5   8   12
prefix:  0   2   7  15   27
         ↑                ↑
    prefix[0]         prefix[4] = prefix[m]

At rank k = 2  (idx = 8):

  left part  = i_0 + i_1                  = 2 + 5  = 7
             = prefix[k]  = prefix[2]     = 7                       ✓ (8 is NOT included)

  right part = i_3                        = 12
             = prefix[m] - prefix[k + 1]
             = prefix[4] - prefix[3]      = 27 - 15 = 12            ✓ (8 is NOT included)

Contrast the off-by-one:
  prefix[m] - prefix[k] = 27 - 7 = 20 = 8 + 12   ← still carries idx itself, hence prefix[k+1]

left = (idx - i_0) + (idx - i_1) + ... + (idx - i_{k-1})

     = (idx + idx + ... + idx)  -  (i_0 + i_1 + ... + i_{k-1})
       └─── k copies of idx ──┘     └── sum of the first k ──┘

     = idx * k - (i_0 + ... + i_{k-1})

     = idx * left_cnt - prefix[k]

right = (i_{k+1} - idx) + (i_{k+2} - idx) + ... + (i_{m-1} - idx)

      = (i_{k+1} + i_{k+2} + ... + i_{m-1})  -  (idx + ... + idx)
        └───── sum of the right part ──────┘     └ m-1-k copies ┘

      = (total_sum - sum_up_to_and_including_idx) - idx * (m - 1 - k)

      = (prefix[m] - prefix[k + 1]) - idx * right_cnt

res[idx] = left + right
         = (idx * left_cnt - prefix[k])  +  ((prefix[m] - prefix[k + 1]) - idx * right_cnt)

One group's indices: [2, 5, 8, 12]        m = 4
rank k:               0  1  2   3

prefix = [0, 2, 7, 15, 27]
          ↑                ↑
       empty sum        prefix[m] = whole group

Take rank k = 2  →  idx = 8, left_cnt = 2, right_cnt = m-1-k = 1

  left  = idx * left_cnt - prefix[k]
        = 8 * 2 - prefix[2]                    prefix[2] = 2 + 5 = 7
        = 16 - 7 = 9                           → |8-2| + |8-5| = 6 + 3 = 9 ✓

  right = (prefix[m] - prefix[k+1]) - idx * right_cnt
        = (27 - 15) - 8 * 1                    prefix[3] = 2 + 5 + 8 = 15
        = 12 - 8 = 4                           → |12-8| = 4 ✓

  res[8] = 9 + 4 = 13

groups:  1 -> [0, 2, 3]      3 -> [1]      2 -> [4]

Group [0, 2, 3]:  m = 3,  prefix = [0, 0, 2, 5]

 k=0  idx=0  left_cnt=0 right_cnt=2   left = 0*0 - prefix[0] = 0
                                      right = (5 - prefix[1]) - 0*2 = 5 - 0 = 5   res[0] = 5 ✓
 k=1  idx=2  left_cnt=1 right_cnt=1   left = 2*1 - prefix[1] = 2 - 0 = 2
                                      right = (5 - prefix[2]) - 2*1 = 3 - 2 = 1   res[2] = 3 ✓
 k=2  idx=3  left_cnt=2 right_cnt=0   left = 3*2 - prefix[2] = 6 - 2 = 4
                                      right = (5 - prefix[3]) - 3*0 = 0           res[3] = 4 ✓

Single-index groups keep res = 0  →  res[1] = res[4] = 0 ✓

def sum_of_distances(nums):
    """
    LC 2615: Calculate sum of |i - j| for all j where nums[j] == nums[i]
    Time: O(n), Space: O(n)
    """
    from collections import defaultdict

    n = len(nums)
    result = [0] * n

    # Step 1: Group indices by value
    index_map = defaultdict(list)
    for i, num in enumerate(nums):
        index_map[num].append(i)

    # Step 2: For each group, calculate distances using prefix sum
    for indices in index_map.values():
        m = len(indices)
        if m == 1:
            continue  # Single element has distance 0

        # prefix[k] = sum of the first k indices  (size m+1, prefix[0] = 0)
        prefix = [0] * (m + 1)
        for k in range(m):
            prefix[k + 1] = prefix[k] + indices[k]

        # Calculate distance for each index in group
        for k in range(m):
            idx = indices[k]

            # Left part: idx * left_cnt - prefix[k]
            left_cnt = k
            left_dist = idx * left_cnt - prefix[k]

            # Right part: (prefix[m] - prefix[k+1]) - idx * right_cnt
            right_cnt = m - 1 - k
            right_dist = (prefix[m] - prefix[k + 1]) - idx * right_cnt

            result[idx] = left_dist + right_dist

    return result

// LC 2615 - Sum of Distances
public long[] distance(int[] nums) {
    int n = nums.length;
    long[] res = new long[n];
    Map<Integer, List<Integer>> map = new HashMap<>();

    // Step 1: Group indices by value
    for (int i = 0; i < n; i++) {
        map.computeIfAbsent(nums[i], k -> new ArrayList<>()).add(i);
    }

    // Step 2: Calculate distances using prefix sum
    for (List<Integer> indices : map.values()) {
        int m = indices.size();
        if (m == 1) continue;

        // prefix[k] = sum of the first k indices  (size m+1, prefix[0] = 0)
        long[] prefix = new long[m + 1];
        for (int k = 0; k < m; k++) {
            prefix[k + 1] = prefix[k] + indices.get(k);
        }

        // Calculate distance for each index
        for (int k = 0; k < m; k++) {
            int idx = indices.get(k);

            // Left: idx * left_cnt - prefix[k]
            long left = (long) idx * k - prefix[k];

            // Right: (prefix[m] - prefix[k+1]) - idx * right_cnt
            long right = (prefix[m] - prefix[k + 1]) - (long) idx * (m - 1 - k);

            res[idx] = left + right;
        }
    }

    return res;
}

def sum_of_distances_optimized(nums):
    """Space-optimized version using running sums"""
    from collections import defaultdict

    n = len(nums)
    result = [0] * n
    index_map = defaultdict(list)

    for i, num in enumerate(nums):
        index_map[num].append(i)

    for indices in index_map.values():
        m = len(indices)
        if m == 1:
            continue

        # Calculate total sum once
        total_sum = sum(indices)

        prefix_sum = 0
        for i, idx in enumerate(indices):
            # Left: idx * i - prefix_sum
            # Right: (total_sum - prefix_sum - idx) - idx * (m - i - 1)
            left_dist = idx * i - prefix_sum
            right_dist = (total_sum - prefix_sum - idx) - idx * (m - i - 1)

            result[idx] = left_dist + right_dist
            prefix_sum += idx

    return result

left  = idx * i           - prefixSum
right = (total - prefixSum - idx) - idx * (m - i - 1)

left + right
  = idx*i - prefixSum + total - prefixSum - idx - idx*m + idx*i + idx
  = total - 2 * prefixSum + idx * (2*i - m)
                             ↑
                    the -idx and +idx cancel

# python
# LC 2615 - Sum of Distances  (collapsed form)
# IDEA: total - 2*prefix[k] + idx*(2k - m) is exactly leftDist + rightDist  (k = rank, m = group size)
# time = O(n), space = O(n)
from collections import defaultdict

def distance(nums):
    groups = defaultdict(list)
    for i, v in enumerate(nums):
        groups[v].append(i)

    res = [0] * len(nums)
    for group in groups.values():
        total, prefix_sum, m = sum(group), 0, len(group)
        for i, idx in enumerate(group):
            res[idx] = total - prefix_sum * 2 + idx * (2 * i - m)
            prefix_sum += idx
    return res

// Java — LC 769 Max Chunks To Make Sorted
// Time: O(n)  Space: O(1)
public int maxChunksToSorted(int[] arr) {
    int chunks = 0, maxSoFar = 0;
    for (int i = 0; i < arr.length; i++) {
        maxSoFar = Math.max(maxSoFar, arr[i]);
        if (maxSoFar == i) chunks++;   // all values 0..i are present in arr[0..i]
    }
    return chunks;
}

# Python — LC 769
def maxChunksToSorted(arr):
    chunks = max_so_far = 0
    for i, val in enumerate(arr):
        max_so_far = max(max_so_far, val)
        if max_so_far == i:
            chunks += 1
    return chunks

// prefixSum of arr == prefixSum of sorted arr  →  same multiset in [0..i]
int chunks = 0, prefixSum = 0, sortedPrefixSum = 0;
for (int i = 0; i < arr.length; i++) {
    prefixSum += arr[i];
    sortedPrefixSum += i;           // sorted array is [0,1,2,...,n-1]
    if (prefixSum == sortedPrefixSum) chunks++;
}

// If values are NOT a permutation, use:
// max(arr[0..i-1]) < min(arr[i..n-1])  →  valid cut point
int[] prefixMax = arr.clone(), suffixMin = arr.clone();
for (int i = 1; i < n; i++) prefixMax[i] = Math.max(prefixMax[i-1], prefixMax[i]);
for (int i = n-2; i >= 0; i--) suffixMin[i] = Math.min(suffixMin[i+1], suffixMin[i]);
int chunks = 0;
for (int i = 0; i < n; i++)
    if (i == 0 || suffixMin[i] > prefixMax[i-1]) chunks++;

grid = [[2, 5, 4],
        [1, 5, 1]]        robot 1 turns down at column i = 1

        col:   0     1     2
row 0:       [ 2 ] [ 5 ]   4        4 survives   ->  TOP    = suffix of row 0
row 1:         1   [ 5 ] [ 1 ]      1 survives   ->  BOTTOM = prefix of row 1
                     ^
        [ ] = zeroed by robot 1     column i is on robot 1's own path -> in NEITHER block

answer = min over i of   max( sum(row0[i+1 ... n-1]) ,  sum(row1[0 ... i-1]) )
                              └──── suffix, shrinks ─┘   └──── prefix, grows ─┘

top    = sum(row 0)          the suffix, starts whole
bottom = 0                   the prefix, starts empty

for i in 0 .. n-1:
    top    -= row0[i]        1. shrink the suffix FIRST  -> column i leaves the top block
    res     = min(res, max(top, bottom))   2. score this split
    bottom += row1[i]        3. grow the prefix AFTER    -> column i joins the bottom block
                                              only for the NEXT split

# python
# LC 2017 - Grid Game
# IDEA: a path in a 2 x n grid IS its turning column, so scan the column and keep
#       suffix(row 0) and prefix(row 1) as two running sums
# time = O(n), space = O(1)
class Solution(object):
    def gridGame(self, grid):
        top = sum(grid[0])      # suffix row0[i+1 ... n-1] once shrunk
        bottom = 0              # prefix row1[0   ... i-1] once grown
        res = float('inf')

        for i in range(len(grid[0])):
            top -= grid[0][i]                    # column i leaves the top block
            res = min(res, max(top, bottom))     # robot 2 takes the bigger block
            bottom += grid[1][i]                 # column i joins the bottom block

        return res

// java
// LC 2017 - Grid Game
// IDEA: minimise, over the turning column, the max of (row 0 suffix, row 1 prefix)
// time = O(n), space = O(1)
public long gridGame(int[][] grid) {
    long top = 0, bottom = 0, res = Long.MAX_VALUE;
    for (int v : grid[0]) top += v;              // n <= 5e4, v <= 1e5 -> 5e9, so long

    for (int i = 0; i < grid[0].length; i++) {
        top -= grid[0][i];
        res = Math.min(res, Math.max(top, bottom));
        bottom += grid[1][i];
    }
    return res;
}

top starts at 2+5+4 = 11, bottom at 0

 i | top -= row0[i] | bottom | max(top, bottom) | res | bottom += row1[i]
---+----------------+--------+------------------+-----+------------------
 0 | 11 - 2 =  9    |   0    |        9         |  9  | 0 + 1 = 1
 1 |  9 - 5 =  4    |   1    |        4    <--  |  4  | 1 + 5 = 6
 2 |  4 - 4 =  0    |   6    |        6         |  4  | 6 + 1 = 7

answer = 4   (robot 1 turns at column 1, robot 2 takes the lone 4 on the top row) ✓

Problem Analysis Flowchart:

1. Need multiple range sum queries?
   ├── YES → Use Template 1 (Basic Prefix Sum)
   └── NO → Continue to 2

2. Looking for subarrays with specific sum/count?
   ├── YES → Continue to 2a
   └── NO → Continue to 3
   
   2a. Exact sum target?
       ├── YES → Use Template 2 (HashMap + Prefix Sum)
       └── NO → Continue to 2b
   
   2b. Divisibility or modulo involved?
       ├── YES → Use Template 3 (Modulo Prefix Sum)
       └── NO → Continue to 2c
   
   2c. Count odd/even or binary transformation?
       ├── YES → Use Template 6 (Transform and Count)
       └── NO → Use Template 2

3. Multiple range updates needed?
   ├── YES → Use Template 4 (Difference Array)
   └── NO → Continue to 4

4. 2D matrix operations?
   ├── YES → Use Template 5 (2D Prefix Sum)
   └── NO → Continue to 5

5. Is every candidate answer described by ONE index (a cut, a pivot, a turning column)?
   ├── YES → Use Template 15 (Prefix + Suffix Split), even when the ask is min(max(...))
   └── NO → Continue to 6

6. Special cases:
   ├── Product instead of sum → Modified Template 1
   ├── Tree path sums → Template 2 + Tree traversal
   ├── Sliding window + prefix → Combine templates
   └── Advanced merge/sort → Custom approach

# For 1D array: sum of subarray [i, j] (inclusive)
subarray_sum = prefix[j + 1] - prefix[i]

# For 2D matrix: sum of rectangle from (r1,c1) to (r2,c2)
rectangle_sum = prefix[r2+1][c2+1] - prefix[r1][c2+1] - prefix[r2+1][c1] + prefix[r1][c1]

# If prefix_sum[j] - prefix_sum[i] = k
# Then prefix_sum[i] = prefix_sum[j] - k
# So check if (current_prefix_sum - k) exists in map

# For divisibility: if (sum[j] - sum[i]) % k = 0
# Then sum[j] % k = sum[i] % k
# So check if (current_sum % k) exists in remainder map

# Convert "find subarray with sum = k" to "find two prefix sums with diff = k"
def subarray_sum_equals_k(nums, k):
    prefix_sum = 0
    count = 0
    prefix_map = {0: 1}  # Critical: handle subarrays from index 0
    
    for num in nums:
        prefix_sum += num
        count += prefix_map.get(prefix_sum - k, 0)
        prefix_map[prefix_sum] = prefix_map.get(prefix_sum, 0) + 1
    
    return count

# Apply multiple range updates [start, end, val] efficiently
def range_addition(length, updates):
    diff = [0] * (length + 1)  # Extra space for end+1 indexing
    
    for start, end, val in updates:
        diff[start] += val      # Mark start
        diff[end + 1] -= val    # Mark end+1 (undo effect)
    
    # Convert difference array to result using prefix sum
    result = []
    current = 0
    for i in range(length):
        current += diff[i]      # This is prefix sum computation!
        result.append(current)
    
    return result

# Many problems can be reduced to simpler prefix sum problems
def count_nice_subarrays(nums, k):
    # Transform: odd numbers → 1, even numbers → 0
    # Problem becomes: count subarrays with sum = k
    binary_array = [1 if x % 2 == 1 else 0 for x in nums]
    return subarray_sum_equals_k(binary_array, k)