Does Heavy Light Decomposition have any advantage over Binary Lifting Technique or using a sparse table? Can we solve some type of problem using HLD which can't be solved using the other mentioned techniques?
Does Heavy Light Decomposition have any advantage over Binary Lifting Technique or using a sparse table? Can we solve some type of problem using HLD which can't be solved using the other mentioned techniques?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 155 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | BledDest | 145 |
Hld is useful when u are given some kind of non-invertible operation queries with updates. For example, consider the problem witht the following 2 queries:
Update the value of node X to Y
Say the GCD of the path u...v
Can this be done in some other way ?
Ah ok, so it should be used when we need to support update queries. That didn't strike me for some reason. Thanks!
Apart from update queries, ofc:
HLD: O(N) preprocessing, O(logN) LCA query, O(N) memory.
Binary lifting: O(NlogN) preprocessing, O(logN) LCA query, O(NlogN) memory.
Sparse table on DFS order: O(NlogN) preprocessing, O(1) LCA query, O(NlogN) memory.
Segment tree on DFS order: O(N) preprocessing, O(logN) LCA query, O(N) memory.
It's easy to see that HLD beats binary lifting by any means (except for simplicity which is actually quite important in CP), sparse table has a better query time but worse preprocessing time and memory complexity while segment tree gives you the same complexities. Not sure if the constant factor for querying segment tree is bigger than the one for LCA query in HLD but I guess so.
HLD: O(N) preprocessing, O(logN) LCA query, O(N) memory.What do you mean by LCA query? LCA can be calculated in O(logN) irrespective of HLD/sparse tables, right?
Maybe I have misunderstood what you meant but if you mean query a given path using HLD, that can take O(logN*logN) time, because you may encounter at most logN light edges and for each light edge you will perform a query on the segment tree representing the heavy path above it.
What I mean by LCA query is find the LCA of two nodes. You can do it with HLD, simply bringing one of the nodes to the next chain, depending on which one is deeper until they happen to be in the same chain.