LC - 2080 - Range Frequency Query - based on Segment tree and Hashtable - could use Binary search in some way to optimize maybe

RangeFreqQuery.java

class RangeFreqQuery {
    private int[] arr;
    private Map<Integer, Integer>[] segTree;

    public RangeFreqQuery(int[] arr) {
        this.arr = arr;
        segTree = new HashMap[4*arr.length];

        buildSegTree(0, 0, arr.length - 1, arr, segTree);
    }

    private void buildSegTree(int ind, int l, int r, int[] arr, Map<Integer, Integer>[] segTree) {
        if (l == r) {
            Map<Integer, Integer> newMap = new HashMap<>();
            newMap.put(arr[l], 1);
            segTree[ind] = newMap;
            return;
        }

        int mid = l + (r - l) / 2;
        buildSegTree(2*ind + 1, l, mid, arr, segTree);
        buildSegTree(2*ind + 2, mid + 1, r, arr, segTree);

        // update the upper node (parent) with the sum of frequencies of the below children
        Map<Integer, Integer> newMap = new HashMap<>();

        for (Map.Entry<Integer, Integer> entry: segTree[2*ind + 1].entrySet())  {
            newMap.put(entry.getKey(), entry.getValue());
        }

        for (Map.Entry<Integer, Integer> entry: segTree[2*ind + 2].entrySet()) {
            newMap.put(entry.getKey(), newMap.getOrDefault(entry.getKey(), 0) + entry.getValue());
        }

        segTree[ind] = newMap;
    }
    
    public int query(int left, int right, int value) {
        return query(0, 0, arr.length - 1, left, right, value);
    }

    private int query(int ind, int l, int r, int start, int end, int value) {
        // if this range is completely out of bounds
        if (l > end || r < start) {
            return 0;
        }

        // if completely within the range
        if (start <= l && r <= end) {
            return segTree[ind].getOrDefault(value, 0);
        }

        // overlapping
        int mid = l + (r - l) / 2;
        return (
            query(2*ind + 1, l, mid, start, end, value) +
            query(2*ind + 2, mid + 1, r, start, end, value)
        );
    }
}

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