Count of Range Sum LeetCode solution in JavaScript

1
/**
2
 * @param {number[]} nums
3
 * @param {number} lower
4
 * @param {number} upper
5
 * @return {number}
6
 */
7
var countRangeSum = function (nums, lower, upper) {
8
  if (nums.length === 1) return 1;
9
  let prefixSums = new Array(nums.length + 1);
10
  prefixSums[0] = 0;
11
  for (let index = 0; index < nums.length; index++) {
12
    if (index == 0) {
13
      prefixSums[index + 1] = nums[index];
14
    } else {
15
      prefixSums[index + 1] = prefixSums[index] + nums[index];
16
    }
17
  }
18

19
  let sortedPrefixSums = prefixSums.slice();
20
  sortedPrefixSums.sort((a, b) => a - b);
21

22
  let ranks = new Map();
23
  for (let index = 0; index < sortedPrefixSums.length; index++) {
24
    ranks.set(sortedPrefixSums[index], index);
25
  }
26

27
  let count = 0;
28
  let tree = new SegTree(sortedPrefixSums);
29
  const reversed = new TreeMap([...ranks.keys()]);
30

31
  function getRanks(val) {
32
    let lowerBound = reversed.floorKey(val + lower - 1);
33
    let minRank = -1;
34
    if (lowerBound !== undefined) {
35
      minRank = ranks.get(lowerBound) + 1;
36
    }
37

38
    let upperBound = reversed.floorKey(val + upper, 0, reversed.length - 1);
39
    let maxRank = -1;
40
    if (upperBound !== undefined) {
41
      maxRank = ranks.get(upperBound);
42
    }
43
    return [minRank, maxRank];
44
  }
45

46
  for (let index = prefixSums.length - 1; index >= 0; index--) {
47
    const [minRank, maxRank] = getRanks(prefixSums[index]);
48
    const c = tree.query(minRank, maxRank);
49
    count += c;
50

51
    const r = ranks.get(prefixSums[index]);
52
    tree.update(r);
53
  }
54

55
  return count;
56
};
57

58
class SegTree {
59
  arr = [];
60
  constructor(arr) {
61
    const n = arr.length;
62
    this.size = n;
63
    this.lastLevelNodeAmount = 2 ** Math.ceil(Math.log2(n));
64
    this.offset = this.lastLevelNodeAmount - 1;
65
  }
66
  update(idx) {
67
    const newIdx = this.offset + idx;
68
    this.arr[newIdx] = (this.arr[newIdx] ?? 0) + 1;
69
    this._update(newIdx, 1);
70
  }
71
  _update(idx, diff) {
72
    const parentIdx = Math.ceil(idx / 2) - 1;
73
    if (!this.arr[parentIdx]) this.arr[parentIdx] = 0;
74

75
    this.arr[parentIdx] += diff;
76

77
    if (parentIdx > 0) this._update(parentIdx, diff);
78
  }
79
  query = (i, j) => {
80
    if (i > j) return 0;
81
    return this._query(i, j, 0, this.lastLevelNodeAmount, 0);
82
  };
83
  _query(i, j, l, r, idx) {
84
    if (i > r || j < l) return 0;
85
    if (i <= l && j >= Math.min(this.size, r) - 1) {
86
      return this.arr[idx] ?? 0;
87
    }
88

89
    const mid = l + Math.floor((r - l) / 2);
90
    const firstChildIdx = 2 * idx + 1;
91
    const secondChildIdx = 2 * idx + 2;
92

93
    if (i >= mid) {
94
      // right
95
      return this._query(i, j, mid, r, secondChildIdx);
96
    } else if (j < mid) {
97
      // left
98
      return this._query(i, j, l, mid, firstChildIdx);
99
    }
100

101
    const leftQuery = this._query(i, j, l, mid, firstChildIdx);
102
    const rightQuery = this._query(i, j, mid, r, secondChildIdx);
103

104
    return leftQuery + rightQuery;
105
  }
106
}
107

108
class TreeMap {
109
  constructor(arr) {
110
    this.arr = arr;
111
  }
112

113
  floorKey(key) {
114
    return this.#binarySearch(key, 0, this.arr.length - 1);
115
  }
116

117
  #binarySearch(target, l, r) {
118
    if (l > r) {
119
      return r < 0 ? undefined : this.arr[this.arr.length - 1];
120
    }
121
    const mid = l + Math.floor((r - l) / 2);
122
    if (this.arr[mid] === target) return this.arr[mid];
123
    else if (this.arr[mid - 1] < target && this.arr[mid] > target)
124
      return this.arr[mid - 1];
125
    else if (this.arr[mid] > target)
126
      return this.#binarySearch(target, l, mid - 1);
127
    else return this.#binarySearch(target, mid + 1, r);
128
  }
129
}