Given an array of up to `200000`

elements, my task is to process up to `200000`

queries, which either ask me to update a single value within the array or ask me to find the number of elements that lie in a given range.

My current idea is to first use *index compression* on the given array, then keep another array that contains the number of occurrences of each number. Then, processing and updating queries could be done using a sum segment tree.

However, I ran into a problem while trying to implement this approach. I realized that updating a single array value could force me to shift the compressed array.

For example, given an array `[1, 5, 3, 3, 2]`

, I would define a compression function `C`

such that

`C[1] = 0; C[2] = 1; C[3] = 2; C[5] = 3; `

Then, the occurrence array would be `[1, 1, 2, 1]`

, and processing sum queries would be efficient. However, if I were instructed to *update* a value, say, change the third element to `4`

, then that throws everything out of balance. The compression function would have to change to

`C[1] = 0; C[2] = 1; C[3] = 2; C[4] = 3; C[5] = 4; `

which would force me to reconstruct my occurrence array, resulting in `O(N)`

update time.

Since `N`

can be up to `200000`

, my approach will not work efficiently enough to solve the problem, although I think I have the right idea with index compression. Can somebody please point me in the right direction?