I'm trying to solve this problem: https://cses.fi/problemset/task/1144/
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 = 0; C = 1; C = 2; C = 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 = 0; C = 1; C = 2; C = 3; C = 4;
which would force me to reconstruct my occurrence array, resulting in
O(N) update time.
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?