Структуры данных

[Smitt&Wesson]

Для Вашей задачи, дерево точно не подойдёт. Для хранения элементов дерева требуется место под хранение ссылок на последующие два элемента (как минимум) т.е. на один бит информации Вы будете затрачивать 32+32+1 бит, для 32-х разрядных машин и 64+64+1 для 64-х разрядных. Булев массив будет затрачивать 8 бит памяти для хранения значения true/false, битовая структура - 32+8 бит памяти или 64+8 для 64-х разрядных машин.
Если память ограничена, я бы поступил так. Создал массив char и при помощи операторов << или >> производил доступ к отдельному биту какждого байта массива. В этом случае массив будет хранить n*8 булевых переменных. Правда за это пидётся "заплатить" скоростью обработки.

очень быстро и много раз изменять значение элемента на различных отрезках [L..R]

Если отрезки постоянные (или редко меняются) их можно хранить на диске, а в памяти хранить только те, с которыми программа работает в данный момент. Если использовать виртуальную память, всё равно часть данных будет записываться на диск в виде кеша.

[Gapro]

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

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

Дерево Фенвика требует столько же памяти, сколько массив из n элементов, т.е. O(n) А сама задача вот http://acm.timus.ru/problem.aspx?space=1&num=1019