| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 160 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | Dominater069 | 154 |
| 8 | awoo | 154 |
| 10 | luogu_official | 150 |
Всем хорошего настроения.
Я заметил, что умею из дерева отрезков с реализацией сверху на массиве [0..n) получать его динамическую версию для интервала [0..INT_MAX) изменением всего пары строк: (simple) (dynamic)
По-моему, забавно, решил поделиться. Сам я раньше динамическую версию дерева отрезков всегда на ссылках писал.
Такое же решение для дерева Фенвика https://sites.google.com/site/indy256/algo_cpp/fenwick_tree_on_map
В каких задачах это бывает полезно? Допустим, когда дается массив размером 10^9, но заполнено там только 10^5 элементов, и требуется вычислять сумму элементов с индексами от i до j? (Тут несколько решений, можно еще сжать координаты и i, j до ближайшего сжатого индекса)
Если на запросы нужно отвечать в онлайне, то сжать не получится.
Но массив размером 10^9 — это редкость. Чаще оно используется как сбалансированное двоичное дерево, То есть, как аналог set'a, где мы еще можем выполнять различные запросы на подотрезках, поиск К-ого элемента, находить количество чисел меньше заданного и тд
Я думаю что лучше всегда использовать
с ссылками, так какmapзанимает много памяти. <--- Я здесь кое что перепутал, думал речь о декартовом дереве. :DЕсли брать хеш-таблицу с открытой адресацией с отношением заполненности 1.5, то памяти на хеш-таблицу уйдёт меньше, чем на дерево с ссылками: (4 байта на координату + 4 байта на ключ) * 1.5 т.к. пустые ячейки = 12. Дерево с ссылками: 4 байта на ключ, 8*2 (или 4*2) байт на ссылки = 12 (или 20).
Чем теоретизировать, проще, кажется проверить. Можешь закатать рукава и написать свою оптимальную реализацию динамического дерева отрезков на ссылках (указателях, а лучше даже индексах, ибо 64-битность, все дела), и сравнить с реализацией снизу на хеш-таблицах с открытой адресацией? Сравнить интересно по времени.
А еще, на ссылках нельзя было написать дерево снизу, а с unordered_map такое сделать можно.
Я туплю или v доходит до 2*INT_MAX ?
Ты не тупишь, туплю я. Fixed (INT_MAX --> INT_MAX / 2).
а что fixed?)
Ну если компилятор правильно переполняет int, то все ок :)
Ну с мапом там константа жёсткая. Помнится, задачи на тимусе ТЛили если так делать.
Ну да, жёсткая... даже с
unordered_map, даже если емуreserveсделать.В задаче B мое решение прошло только с ссылками. а с map-ом падает на 7 тесте(память).