Нужная такая структура данных. Массив фиксированной длины, с кольцевой индексацией. Из него надо делать выборку и добавление, но не по индексам а по диапазону индексов. Выборка означает получение суммы элементов от указанного до указанного. Добавление, ко всем элементам от указанного до указанного добавить указанное число. Эти две операции надо делать так быстро как возможно. Лишней памяти нет.
Сейчас предполагаю использование кумулятивной суммы, чтобы делать быструю выборку. Но добавление все таки потребует прохода по всему диапазону. Еще надо особо обрабатывать переход через границу массива, т.к. кольцевая индексация.
Есть еще какие-то интересные способы? Могу дать дополнительное условие, добавления не обязательно исполнять немедленно, можно накопить несколько и исполнить их все вместе.
Спасибо.