|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
20.10.2011, 16:24 | #1 |
Форумчанин
Регистрация: 30.07.2009
Сообщений: 256
|
Структуры данных
У меня есть массив 1..10^9, каждый элемент отрезка - true или false, мне нужно очень быстро и много раз изменять значение элемента на различных отрезках [L..R]. Память ограничена - 16 Мб.
Я не могу подобрать подходящую структуру данных. Мне кажется можно реализовать деревом Фенвика, однако как реализвать я не могу понять. P.S. Нет отдельного раздела про структуры данных, поэтому запостил сюда. |
20.10.2011, 16:42 | #2 |
Старожил
Регистрация: 19.08.2009
Сообщений: 2,119
|
Gapro
У меня есть массив 1..10^9, каждый элемент отрезка - true или false Я не могу подобрать подходящую структуру данных std::vector<bool>
А вы почему со мной не соглашаетесь, у вас что, импотенция? (c) ACE Valery
|
20.10.2011, 17:12 | #3 |
Форумчанин
Регистрация: 30.07.2009
Сообщений: 256
|
|
20.10.2011, 20:34 | #4 | |
Форумчанин
Регистрация: 02.02.2010
Сообщений: 599
|
Цитата:
"Лишь то читается легко, что написано с трудом; что в час написано, то в час и позабыто."
|
|
21.10.2011, 09:13 | #5 |
Форумчанин
Регистрация: 30.07.2009
Сообщений: 256
|
|
21.10.2011, 21:03 | #6 |
Форумчанин
Регистрация: 02.02.2010
Сообщений: 599
|
Дерево никогда не будет меньше массива.
"Лишь то читается легко, что написано с трудом; что в час написано, то в час и позабыто."
|
22.10.2011, 20:06 | #7 |
Форумчанин
Регистрация: 30.07.2009
Сообщений: 256
|
|
22.10.2011, 20:50 | #8 | |
Форумчанин
Регистрация: 02.02.2010
Сообщений: 599
|
Цитата:
"Лишь то читается легко, что написано с трудом; что в час написано, то в час и позабыто."
|
|
22.10.2011, 22:05 | #9 |
Форумчанин
Регистрация: 30.07.2009
Сообщений: 256
|
|
22.10.2011, 23:31 | #10 |
Форумчанин
Регистрация: 02.02.2010
Сообщений: 599
|
В дереве Фенвика, если мне не изменяет память, требуется 2n памяти. Я имел ввиду массив префиксных сумм, когда говорил, что это деревом не является.
"Лишь то читается легко, что написано с трудом; что в час написано, то в час и позабыто."
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Структуры данных | Shadow94 | Общие вопросы C/C++ | 8 | 22.04.2011 11:50 |
Структуры данных | SlayerLiving | C++ Builder | 2 | 07.03.2011 20:26 |
Структуры данных | LeNus'Ka | Помощь студентам | 4 | 23.11.2010 17:43 |
С++ Структуры данных | DarkSwan | Помощь студентам | 0 | 27.10.2010 12:21 |
Структуры данных в С++ | ArniLand | Общие вопросы C/C++ | 2 | 14.07.2010 18:34 |