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
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
20:36:46
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
20:36:46
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 22.11.2024 20:58:14 (j1).
Десктопная версия, переключиться на мобильную.
При поддержке
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.