Я не буду просить, чтобы вы ее решили. Просто кажется интересным.

Пусть дан некоторый массив a размером N < 2³⁰ 32-битных целых чисел. Требуется выполнить M запросов вида "сумма чисел на данном отрезке" за O(N+M), используя как можно меньше дополнительной памяти.

Очевидно, что существует решение, использующее 30 * N бит дополнительной памяти.

Update 1.
Если допускать сложность O(N+M*log(N)), то можно добиться 6 * N бит дополнительной памяти.

=============

В связи с особыми шаманствами, думаю, надо формализовать задачу немного по-другому.

Пусть дан некоторый массив a размером N из β-битных целых чисел. Требуется выполнить M запросов вида "сумма чисел на данном отрезке" за O(N+M), используя как можно меньше дополнительной памяти. Операция сложения и обращения по индексу выполняются за О(1), умножение процессор не поддерживает.

Очевидно, что существует решение, использующее бит дополнительной памяти.

Если допускать сложность O(N+M*log(N)), то можно добиться сколь угодно мало дополнительной памяти ценой сколь угодно большой константы во времени.