12 Aug 2023•PHP•Hard

Count of Range Sum

count subarrays with sum in range [lower, upper] using prefix sums and merge sort counting.

convert to prefix sum problem: count pairs (i, j) where prefix[j] - prefix[i] is in [lower, upper]. use merge sort to count valid pairs during merging.

during merge, for each left element, find range of right elements where difference is in [lower, upper]. the sorted nature of merge sort makes this efficient with two pointers.

approach

build prefix sum array
use merge sort to count valid pairs
during merge, count pairs with sum in range
combine counts from left, right, and cross pairs

complexity

O(n log n) time from merge sort. O(n) space for prefix sums and temporary arrays.

Solution files

PHP•count-of-range-sum/solution.php

class Solution {

function countRangeSum($nums, $lower, $upper) {
    $count = class="syntax-number">0;
    $presum = [class="syntax-number">0];
    
    foreach ($nums as $num) {
        $presum[] = $presum[count($presum) - class="syntax-number">1] + $num;
    }
    
    $count = $this->mergeSort($presum, $lower, $upper, class="syntax-number">0, count($presum) - class="syntax-number">1);
    
    return $count;
}

function mergeSort(&$presum, $lower, $upper, $left, $right) {
    if ($left >= $right) return class="syntax-number">0;
    
    $mid = $left + intdiv($right - $left, class="syntax-number">2);
    $count = $this->mergeSort($presum, $lower, $upper, $left, $mid) + $this->mergeSort($presum, $lower, $upper, $mid + class="syntax-number">1, $right);
    $temp = [];
    $p1 = $p2 = $p3 = $mid + class="syntax-number">1;
    
    for ($p1 = $left, $right_start = $mid + class="syntax-number">1; $p1 <= $mid; $p1++) {
        while ($p2 <= $right && $presum[$p2] - $presum[$p1] < $lower) $p2++;
        while ($p3 <= $right && $presum[$p3] - $presum[$p1] <= $upper) $p3++;
        $count += $p3 - $p2;
        
        while ($right_start <= $right && $presum[$right_start] < $presum[$p1]) $temp[] = $presum[$right_start++];
        $temp[] = $presum[$p1];
    }
    
    while ($right_start <= $right) $temp[] = $presum[$right_start++];
    
    for ($i = $left, $j = class="syntax-number">0; $i <= $right; $i++, $j++) {
        $presum[$i] = $temp[$j];
    }
    
    return $count;
}
}