Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Count of Range Sum

Problem (restated)

Count pairs i ≤ j such that the sum nums[i] + … + nums[j] lies in [lower, upper].

Intuition

The range sum is pref[j+1] - pref[i]. For a new prefix p = pref[j+1], we need previous prefixes q with p - upper ≤ q ≤ p - lower. A Fenwick tree of compressed prefix values answers that range count, then we insert p. Prefixes can overflow 32-bit; store them as 64-bit.

Approaches

Fenwick on prefix sums

Unverified

Time O(n log n)Space O(n)

Idea. Build pref. Compress {pref, pref-lower, pref-upper}. For each p in order: query rangeSum(rank[p-upper], rank[p-lower]), then update(rank[p], 1). Query before insert: pref[0] goes in first (empty query), then each pref[j+1] sees pref[0]…pref[j].

Walkthrough. [-2,5,-1], [lower,upper]=[-2,2]. Three valid windows: [-2], [-2,5,-1], [-1].

Trade-offs. Same “query then insert” as LC 315, on prefix values instead of elements. Merge-sort on prefixes is the divide-and-conquer twin.

Solution

class BIT {
  private n: number;
  private tree: number[];
  constructor(n: number) {
    this.n = n;
    this.tree = new Array<number>(n + 1).fill(0);
  }
  update(i: number, delta: number): void {
    for (i++; i <= this.n; i += i & -i) this.tree[i]! += delta;
  }
  prefixSum(i: number): number {
    if (i < 0) return 0;
    let s = 0;
    for (i++; i > 0; i -= i & -i) s += this.tree[i]!;
    return s;
  }
  rangeSum(l: number, r: number): number {
    if (r < l) return 0;
    return this.prefixSum(r) - (l > 0 ? this.prefixSum(l - 1) : 0);
  }
}

export function countRangeSum(nums: number[], lower: number, upper: number): number {
  const pref: number[] = [0];
  for (const x of nums) pref.push(pref[pref.length - 1]! + x);
  const all = new Set<number>(pref);
  for (const p of pref) {
    all.add(p - lower);
    all.add(p - upper);
  }
  const vals = [...all].sort((a, b) => a - b);
  const rank = new Map<number, number>();
  vals.forEach((v, i) => rank.set(v, i));
  const bit = new BIT(vals.length);
  let ans = 0;
  for (const p of pref) {
    const lo = rank.get(p - upper)!;
    const hi = rank.get(p - lower)!;
    ans += bit.rangeSum(lo, hi);
    bit.update(rank.get(p)!, 1);
  }
  return ans;
}

class BIT {
  private n: number;
  private tree: number[];
  constructor(n: number) {
    this.n = n;
    this.tree = new Array<number>(n + 1).fill(0);
  }
  update(i: number, delta: number): void {
    for (i++; i <= this.n; i += i & -i) this.tree[i]! += delta;
  }
  prefixSum(i: number): number {
    if (i < 0) return 0;
    let s = 0;
    for (i++; i > 0; i -= i & -i) s += this.tree[i]!;
    return s;
  }
  rangeSum(l: number, r: number): number {
    if (r < l) return 0;
    return this.prefixSum(r) - (l > 0 ? this.prefixSum(l - 1) : 0);
  }
}

export function countRangeSum(nums: number[], lower: number, upper: number): number {
  const pref: number[] = [0];
  for (const x of nums) pref.push(pref[pref.length - 1]! + x);
  const all = new Set<number>(pref);
  for (const p of pref) {
    all.add(p - lower);
    all.add(p - upper);
  }
  const vals = [...all].sort((a, b) => a - b);
  const rank = new Map<number, number>();
  vals.forEach((v, i) => rank.set(v, i));
  const bit = new BIT(vals.length);
  let ans = 0;
  for (const p of pref) {
    const lo = rank.get(p - upper)!;
    const hi = rank.get(p - lower)!;
    ans += bit.rangeSum(lo, hi);
    bit.update(rank.get(p)!, 1);
  }
  return ans;
}

Template connection

BIT over compressed keys, walking prefixes left to right. LC 493 is the same idea with the predicate a > 2b.

Reflection

A subarray sum is the difference of two prefixes. For each prefix p, count earlier prefixes between p - upper and p - lower.
Query, then insert. pref[0] enters on an empty query. Compression orders negative sums too.
The pair satisfies i < j. An empty array is 0. If the whole array is one valid range, count it plus the ranges inside it.