Prefix SumHardO(n log n) time · O(n) space

Count Range Sum

Mahabharata — Vyasa's Merge Count — Counting All Subarrays Within a Sacred Range

न्यूनातिरिक्तयोः मध्ये यः योगः स्थितः। गण्यतां तत् — विभाजनेन गणना शीघ्रा॥

*Count those sums that lie between the lower and upper bounds. Division and counting — that is the swift method.*

The Story

Vyasa posed the most advanced prefix sum challenge: count the number of subarrays whose sum falls within [lower, upper]. For `nums = [-2, 5, -1]`, `lower = -2`, `upper = 2`, the answer is 3 (subarrays [-2], [-2,5,-1], [-1]).

The naive O(n²) approach checks all pairs. The O(n log n) solution uses merge sort on prefix sums.

**Key insight:** Sum of subarray [j+1..i] = pre[i] - pre[j]. We want `lower <= pre[i] - pre[j] <= upper`, i.e., `pre[i] - upper <= pre[j] <= pre[i] - lower`.

For each i, count valid j < i in the sorted left half during merge sort.

During the merge of two sorted halves [lo..mid] and [mid+1..hi]: - For each right half index i, find the window [k1, k2) in the left half where `pre[i]-upper <= pre[j] <= pre[i]-lower` - Since both halves are sorted, k1 and k2 only move right as i increases → amortized O(n) across all i

Vyasa traced: pre = [0, -2, 3, 2], lower=-2, upper=2.

Merge sort reveals 3 valid pairs in O(n log n).

This is the most sophisticated prefix sum problem — combining prefix sums with divide-and-conquer counting.

The Scholar's First Instinct

Try all O(n²) pairs of (i,j). Compute prefix[i]-prefix[j]. Count those in [lower,upper].

java

public int countRangeSumBruteForce(int[] nums, int lower, int upper) {
    int n = nums.length, count = 0;
    long[] pre = new long[n + 1];
    for (int i = 0; i < n; i++) pre[i+1] = pre[i] + nums[i];
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < i; j++)
            if (pre[i]-pre[j] >= lower && pre[i]-pre[j] <= upper) count++;
    return count;
}

Vyasa's Merge Sort Wisdom

During merge sort of prefix sums, count valid pairs across left and right halves. For each right index i, maintain two pointers (k1, k2) into left half for the window [pre[i]-upper, pre[i]-lower]. Since left is sorted and i increases, k1/k2 only advance — O(n) amortized counting per merge level.

java

public int countRangeSum(int[] nums, int lower, int upper) {
    long[] pre = new long[nums.length + 1];
    for (int i = 0; i < nums.length; i++) pre[i+1] = pre[i] + nums[i];
    return mergeCount(pre, 0, pre.length - 1, lower, upper);
}

private int mergeCount(long[] pre, int lo, int hi, int lower, int upper) {
    if (lo >= hi) return 0;
    int mid = lo + (hi - lo) / 2;
    int count = mergeCount(pre, lo, mid, lower, upper)
              + mergeCount(pre, mid+1, hi, lower, upper);
    // Count valid pairs across the two halves
    int k1 = lo, k2 = lo;
    for (int i = mid + 1; i <= hi; i++) {
        while (k1 <= mid && pre[i] - pre[k1] > upper) k1++;
        while (k2 <= mid && pre[i] - pre[k2] >= lower) k2++;
        count += k2 - k1;
    }
    // Standard merge sort
    long[] sorted = Arrays.copyOfRange(pre, lo, hi + 1);
    Arrays.sort(sorted);
    System.arraycopy(sorted, 0, pre, lo, sorted.length);
    return count;
}

Step-by-Step Walkthrough

pre=[0,-2,3,2], lower=-2, upper=2

Merge([0,-2],[3,2]):
  For i=mid+1=2, pre[2]=3:
    k1: 3-pre[0]=3>2→k1++. 3-pre[1]=-2+2=5>2→k1++. k1=2 (past mid)
    k2: same, k2=2. count+=0
  For i=3, pre[3]=2:
    k1: 2-pre[0]=2<=2. k1=0
    k2: 2-pre[0]=2<-2? No. 2-pre[1]=4>=-2? yes→k2++. k2=2
    Hmm, re-check: k2 advances while pre[i]-pre[k2]>=lower
    pre[3]-pre[0]=2>=-2 → k2++. pre[3]-pre[1]=4>=-2 → k2++. k2=2
    count+=2-0=2
  Plus recursive counts=1
Total=3 ✅

Deep Insight

**Why merge sort works:** The counting step works when the left half is sorted — then k1 and k2 are monotone as i increases. Merge sort naturally provides this sorted property after recursive calls.

**Two pointers k1, k2 in left half:** - k1: leftmost where pre[i]-pre[k1] <= upper (upper bound) - k2: leftmost where pre[i]-pre[k2] < lower (lower bound) - Valid count = k2 - k1 (indices in window)

**Alternative: Balanced BST/Fenwick tree** for O(n log n) but more complex implementation.

Complexity Analysis

Approach	Time	Space	Note
Brute Force	O(n²)	O(n)	All prefix sum pairs checked
Optimal	O(n log n)	O(n)	Merge sort with O(n) counting per level, O(log n) levels

Pattern Recognition

✅ Count subarrays with sum in [lower, upper]
✅ Prefix sums + divide-and-conquer
✅ Merge sort enables monotone two-pointer counting
✅ Hardest prefix sum problem — requires merge sort insight

**LeetCode Trigger Phrases:**
→ "count of range sum"
→ "subarrays with sum between lower and upper"
→ "O(n log n)" + count + prefix sum

Bhagavad Gita 18.18

ज्ञानं ज्ञेयं परिज्ञाता त्रिविधा कर्मचोदना। करणं कर्म कर्तेति त्रिविधः कर्मसंग्रहः॥

Knowledge, the object of knowledge, and the knower — these three motivate action. The instrument, the action, and the doer — these three constitute the totality of action.

Connection: Merge sort embodies the Gita's principle of structured division: knowledge (prefix sums), objects (the pairs to count), and the knower (the counting logic) come together at each merge step. The divide-and-conquer mirrors the three components of action — dividing the problem (karma), executing the count (kriya), and combining results (kartā). Each merge level adds O(n) work with growing wisdom about the whole structure.