I know how to build and perform queries on a merge sort tree. But how to do point updates in the merge sort tree efficiently
I know how to build and perform queries on a merge sort tree. But how to do point updates in the merge sort tree efficiently
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | jiangly | 3810 |
| 2 | Benq | 3676 |
| 3 | Kevin114514 | 3655 |
| 4 | maroonrk | 3463 |
| 5 | strapple | 3447 |
| 6 | Um_nik | 3387 |
| 7 | heuristica | 3322 |
| 8 | turmax | 3317 |
| 9 | tourist | 3307 |
| 10 | jiangbowen | 3291 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 156 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | Um_nik | 141 |
| 5 | Errichto | 139 |
| 6 | adamant | 137 |
| 7 | AmShZ | 135 |
| 8 | BledDest | 132 |
| 9 | maroonrk | 131 |
| 10 | qwexd | 129 |
Have you checked this ?
See the last part.
Yes I have already read this article but just wanted to know if there is some other technique apart from policy based data structures to perform updates
You can keep implicit segment tree in each node so that you can update and query in O(log^2(N)).
Thanks for above technique but I have never implemented implicit segment tree so I have no idea about it. Can you provide any link regarding the same or give brief idea about implicit segment tree??
A past discussion here: Dynamic Segment Trees. Of course, you can google for more).
Sample problems: SPOJ-BLUNIQ SPOJ-ADACROP SPOJ-XXXXXXXX
Sample implementation for ADACROP: code
Check out this blog on the implementation of Point updates in merge sort trees.