To solve problems involving prefix sums and binary search (common for non-negative arrays), we can leverage the monotonic nature of prefix sums to efficiently find solutions. Below, we focus on two typical problems:

Problem 1: Maximum Length of Subarray with Sum ≤ k

Given a non-negative array, find the longest subarray where the sum of elements is ≤ k.

Approach

1. Prefix Sum: Compute the prefix sum array (non-decreasing since the array is non-negative).
2. Binary Search: For each prefix sum, find the smallest index j such that prefix[i] - prefix[j] ≤ k (using binary search on the prefix array up to i-1).
3. Max Length: Calculate the length of the subarray ending at i-1 and update the maximum length.

Solution Code

import bisect

def max_length_subarray_sum_le(arr, k):
    prefix = [0]
    current_sum = 0
    max_len = 0
    for num in arr:
        current_sum += num
        prefix.append(current_sum)
        target = current_sum - k
        # Find first j where prefix[j] >= target (bisect_left)
        pos = bisect.bisect_left(prefix, target, 0, len(prefix)-1)
        current_len = len(prefix)-1 - pos
        if current_len > max_len:
            max_len = current_len
    return max_len

Problem 2: Number of Subarrays with Sum < k

Given a non-negative array, count the number of subarrays where the sum of elements is < k.

Approach

1. Prefix Sum: Compute the prefix sum array.
2. Binary Search: For each prefix sum, find the number of valid j such that prefix[i] - prefix[j] < k (using bisect_right to count elements ≤ prefix[i]-k).
3. Count: Add the valid subarrays count for each i.

Solution Code

import bisect

def count_subarrays_sum_lt(arr, k):
    prefix = [0]
    current_sum = 0
    count = 0
    for num in arr:
        current_sum += num
        prefix.append(current_sum)
        target = current_sum - k
        # Number of j where prefix[j] <= target (bisect_right)
        invalid = bisect.bisect_right(prefix, target, 0, len(prefix)-1)
        count += (len(prefix)-1) - invalid
    return count

Key Takeaways

• Prefix Sum: Converts subarray sum problems into prefix sum differences.
• Binary Search: Uses the monotonicity of prefix sums (non-decreasing) to find solutions in O(log n) per element, leading to O(n log n) overall time complexity.
• Math: Prefix sum is a mathematical tool to simplify subarray sum calculations.

These approaches are efficient and scalable for large arrays, making them ideal for such problems. Choose the solution based on the problem's requirements (max length or count).

作者声明:本文包含人工智能生成内容。