1
class RangeFreqQuery {
2
  // Use map's key to store arr's value, map's value to keep <value's location, cummulative arr's
3
  // value count>
4
  HashMap<Integer, TreeMap<Integer, Integer>> map;
5

6
  public RangeFreqQuery(int[] arr) {
7
    // O(nlog(n))
8
    map = new HashMap<>();
9
    for (int i = 0; i < arr.length; i++) {
10
      map.putIfAbsent(arr[i], new TreeMap<>());
11
      TreeMap<Integer, Integer> tree = map.get(arr[i]);
12
      // i = value's location
13
      // tree.size() = cummulative arr's value count - 1
14
      tree.put(i, tree.size());
15
    }
16
  }
17

18
  public int query(int left, int right, int value) {
19
    // O(log(n))
20

21
    // check if value exist in map
22
    if (!map.containsKey(value)) {
23
      return 0;
24
    }
25
    TreeMap<Integer, Integer> tree = map.get(value);
26

27
    // check if there exist position >= left and position <= right
28
    // if not, return 0
29
    if (tree.ceilingKey(left) == null || tree.floorKey(right) == null) {
30
      return 0;
31
    }
32
    // get leftMost position's cummulative count
33
    int leftMost = tree.get(tree.ceilingKey(left));
34
    // get rightMost position's cummulative count
35
    int rightMost = tree.get(tree.floorKey(right));
36

37
    return rightMost - leftMost + 1;
38
  }
39
}
40

41
/**
42
 * Your RangeFreqQuery object will be instantiated and called as such: RangeFreqQuery obj = new
43
 * RangeFreqQuery(arr); int param_1 = obj.query(left,right,value);
44
 */