I am trying to solve cses salary queries (https://cses.fi/problemset/task/1144/)
Question: I will make a frequency array of salaries and I will use coordinate compression but while update I have to rebuild coordinate compression and there will be a mess.
How to solve this type of problem? I saw a blog in stackoverflow but I could not implement that solution of implicit segment tree.
The solution to your problem is very simple. Instead of coordinate compressing just the initial array, build a new array which is the union of the intial array and all the update query values. Perform coordinate compression on this instead. Your array size will be atmost N+Q. To perform update queries, simply find the compressed equivalent of the update query value.