We are given an integer array (Arr) and an array of queries.

A query will be one of the two types below.

Type 1, format: [1, idx, val], where you are to update Arr[idx]=val, and we do not need to return anything

Type 2, format [2, left_idx, right_idx], where you are to count the number of elements with odd frequency within the left_idx and right_idx inclusive, and we return the count. The index is 1-based indexing

Examples:

Arr = [1,3,5,5]

queries = [[2,1,4], [1,4,2], [2,1,4]]

The output should be [2, 4]

For queries[0], which is [2,1,4], the frequency of the elements is {1:1, 3:1, 5:2} so there are 2 elements (1,3) with odd frequency and the output for this query is 2.

queries[1] changes Arr from [1,3,5,5] to [1,3,5,4], and there will be no output.

queries[2], which is [2,1,4], the frequency of the elements is {1:1, 3:1, 5:1, 4:1}, and there are 4 elements (1,3,5,4) with odd frequency and the output will be 4.

Hence the overall output is [2,4].

I tried solving this question by doing Type 1 query in O(1) (just updating the array) time and Type 2 query in O(n) time (iterating from left to right to get the answer), but this failed the time limit given.

I was wondering if there is any solution with a better time complexity.