Структуры данных - Общие вопросы C/C++

Gapro · 20.10.2011, 16:24

У меня есть массив 1..10^9, каждый элемент отрезка - true или false, мне нужно очень быстро и много раз изменять значение элемента на различных отрезках [L..R]. Память ограничена - 16 Мб.
Я не могу подобрать подходящую структуру данных. Мне кажется можно реализовать деревом Фенвика, однако как реализвать я не могу понять.

P.S. Нет отдельного раздела про структуры данных, поэтому запостил сюда.

Rififi · 20.10.2011, 16:42

Gapro

У меня есть массив 1..10^9, каждый элемент отрезка - true или false
Я не могу подобрать подходящую структуру данных

std::vector<bool>

Gapro · 20.10.2011, 17:12

Цитата:

Сообщение от Rififi

Gapro

std::vector<bool>

Нельзя очень быстро изменять значение на всем отрезке

Syuf · 20.10.2011, 20:34

Цитата:

У меня есть массив 1..10^9 ... Память ограничена - 16 Мб

Даже при битовом сжатии 125Мб.

Gapro · 21.10.2011, 09:13

Цитата:

Сообщение от Syuf

Даже при битовом сжатии 125Мб.

Это еще одна причина по которой мне нужно какое-нибудь дерево или другая структура данных

Syuf · 21.10.2011, 21:03

Дерево никогда не будет меньше массива.

Gapro · 22.10.2011, 20:06

Цитата:

Сообщение от Syuf

Дерево никогда не будет меньше массива.

Однако в дереве мы можем хранить только то, что нам нужно, а не весь массив, например сумма на отрезке.

Syuf · 22.10.2011, 20:50

Цитата:

Однако в дереве мы можем хранить только то, что нам нужно, а не весь массив, например сумма на отрезке

Поконкретней? Если мы и храним суммы на отрезке, то их как минимум N. (И это не дерево)

Gapro · 22.10.2011, 22:05

Цитата:

Сообщение от Syuf

Поконкретней? Если мы и храним суммы на отрезке, то их как минимум N. (И это не дерево)

Да вы правы в том, что 16 мб все равно не хватит, однако деревом такая структура быть может- взять к примеру дерево Фенвика

Syuf · 22.10.2011, 23:31

В дереве Фенвика, если мне не изменяет память, требуется 2n памяти. Я имел ввиду массив префиксных сумм, когда говорил, что это деревом не является.

20.10.2011, 16:24	#1
Gapro Форумчанин Регистрация: 30.07.2009 Сообщений: 256	Структуры данных У меня есть массив 1..10^9, каждый элемент отрезка - true или false, мне нужно очень быстро и много раз изменять значение элемента на различных отрезках [L..R]. Память ограничена - 16 Мб. Я не могу подобрать подходящую структуру данных. Мне кажется можно реализовать деревом Фенвика, однако как реализвать я не могу понять. P.S. Нет отдельного раздела про структуры данных, поэтому запостил сюда.

20.10.2011, 16:42	#2
Rififi Старожил Регистрация: 19.08.2009 Сообщений: 2,119	Gapro У меня есть массив 1..10^9, каждый элемент отрезка - true или false Я не могу подобрать подходящую структуру данных std::vector<bool> А вы почему со мной не соглашаетесь, у вас что, импотенция? (c) ACE Valery

21.10.2011, 21:03	#6
Syuf Форумчанин Регистрация: 02.02.2010 Сообщений: 599	Дерево никогда не будет меньше массива. "Лишь то читается легко, что написано с трудом; что в час написано, то в час и позабыто."

22.10.2011, 23:31	#10
Syuf Форумчанин Регистрация: 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