What is coordinate compression?

Блог пользователя Chasty

Автор Chasty, история, 8 лет назад, По-английски

Hi all. Could some please make me understand what it is with an example? I'll appreciate it. DO you have some problems to apply it?

Chasty
8 лет назад
14

Комментарии (12)

Показать архивные | Написать комментарий?

SuuTTT

5 лет назад, # |

← Rev. 3 →

In Chinese: 离散化(ie. map larger values to smaller distinct values)

→ Ответить

xodeChemist

4 года назад, # |

please explain cordinate compression someone i can't solve a problem relating to this please help me

→ Ответить

wet_water

4 года назад, # |

Let's say that in a problem, you're required to store N (1 <= N <= 10^5) elements and perform some operations on those elements (say put them in a Segment Tree). Normally, if the elements were also in the range (1, 10^5), inserting them into a data structure would be a cinch.

Say, for example, the elements are now in the range (1, 10^12). Now simply inserting elements into a Segment Tree is not possible because you cannot allocate memory for 10^12 integers. This is where coordinate compression comes into play.

Let's read in all of the possible numbers, sort them, and assign each of them a number based off of increasing order. Because N is <= 10^5, the maximum number you assign is going to be 10^5. Thus, by compressing the "coordinates", we maintain the relative order of points in a memory-efficient manner.

I hope this helps!

→ Ответить

Suri429

4 года назад, # ^ |

Hey, thanks for the nice explanation. I have a doubt,

If we have numbers ranging 0,10^9 and i want to update and access their frequency in O(1). Unordered_map,map gave me TLE. Can there be a better than O(lgn) way, using coordinates compression to solve this problem ?

Thanks !

→ Ответить