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
→ Pay attention
→ Streams
→ Top rated
| # | User | Rating |
|---|---|---|
| 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 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 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 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2026 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Sep/24/2026 17:55:36 (g2).
Desktop version, switch to mobile version.
Supported by
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.