Count Subarrays with Sum in a Range
Given an integer array $A_1, A_2, \dots, A_n$ (which may contain negative numbers) and integer bounds $L$ and $R$, count the number of contiguous subarrays whose sum falls in the range $[L, R]$.
Design an $O(n \log n)$ algorithm. Your solution should handle negative numbers, 64-bit overflow, and use coordinate compression for stability.
**Constraints:**
-
\leq n \leq 10^5$
- $-10^9 \leq A_i \leq 10^9$
- $-10^{18} \leq L \leq R \leq 10^{18}$
**Example 1:**
- Input: $A = [1, 2, -1, 3]$, $L = 2$, $R = 4$
- Output: $6$
- Explanation: The subarrays with sums in $[2, 4]$ are: $[1,2]$ (sum 3), $[1,2,-1]$ (sum 2), $[2]$ (sum 2), $[2,-1,3]$ (sum 4), $[-1,3]$ (sum 2), $[3]$ (sum 3). That gives 6 valid subarrays.
**Example 2:**
- Input: $A = [-1, -1, 1]$, $L = -1$, $R = 0$
- Output: $4$
- Explanation: The subarrays with sums in $[-1, 0]$ are: $[-1]$ (index 0, sum -1), $[-1]$ (index 1, sum -1), $[-1, 1]$ (sum 0), and $[-1, -1, 1]$ (sum -1). That gives 4 valid subarrays.
Open the full interactive solver, hints, and worked solution →