CODEWITHSUNDEEP
algorithmdata-structuresarray-algorithmssegment-treerange-query
bharat aaryavrat
bharat aaryavrat

Reputation: 1

CSES range query section question salary queries problem

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.

Upvotes: 0

Views: 163

Answers (1)

Vihari Vemuri
Vihari Vemuri

Reputation: 51

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.

Upvotes: 0

Related Questions