1
var RangeFreqQuery = function (arr) {
2
  this.array = arr;
3
  this.subRangeSize = Math.sqrt(this.array.length) >> 0;
4
  this.subRangeFreqs = [];
5

6
  let freq = {};
7

8
  for (let i = 0; i < arr.length; i++) {
9
    const num = arr[i];
10

11
    if (i >= this.subRangeSize && i % this.subRangeSize === 0) {
12
      this.subRangeFreqs.push({ ...freq });
13
      freq = {};
14
    }
15

16
    freq[num] = (freq[num] || 0) + 1;
17
  }
18

19
  this.subRangeFreqs.push(freq);
20
};
21

22
RangeFreqQuery.prototype.query = function (left, right, value) {
23
  let fr = 0;
24

25
  const leftIdx = (left / this.subRangeSize) >> 0,
26
    rightIdx = (right / this.subRangeSize) >> 0;
27

28
  for (let i = leftIdx; i <= rightIdx; i++) {
29
    fr += this.subRangeFreqs[i][value] || 0;
30
  }
31

32
  for (let i = leftIdx * this.subRangeSize; i < left; i++) {
33
    fr -= this.array[i] === value ? 1 : 0;
34
  }
35

36
  for (
37
    let i = right + 1;
38
    i < Math.min((rightIdx + 1) * this.subRangeSize, this.array.length);
39
    i++
40
  ) {
41
    fr -= this.array[i] === value ? 1 : 0;
42
  }
43
  return fr;
44
};