Кольцевой массив с доступом по диапазону индексов

дерево отрезков, дерево фенвика, да что угодно твоей фантазии

кольцевая индексация

просто считай сумму/прибавляй на двух отрезках в случае l > r

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

Как то так:

typedef struct
{
    int len;
    my_element_type_t * buf;
}
ring_buf_t;

//Переход через границу кольца:
i++;
i %= buff->len; //Len - длина массива.

Дальше сам.

самую сложную часть подсказал, ну а дальше ТС и сам справится

Это ОН?

Дерево слишком сложно, вычислительно. Значительная часть запросов будет длины 1-3 элемента. Пока откатываюсь к тривиальной реализации. А для длинных запросов сумм надо будет наверно делать заранее рассчитанный массив сумм, с учетом выхода за границы, чтобы избавится от условий и разбиения отрезка на два.

Значительная часть запросов будет длины 1-3 элемента.

так бы сразу и сказал, а то я думал, что длина запроса — O(N)

прибавление тоже на таких маленьких отрезках?

Да, но отрезки не всегда будут такими, могут увеличится до 30, но в этом случае можно ограничится только запросами суммы, а изменения вносить при длинах не больше 5 например. Общая длина пока предполагается 300-600 элементов. Памяти хватило бы и на 6k элементов и больше, но длины тогда станут больше, они считаются как доля от общей длины, а сама длина это лишь разрешение.

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

Если для некольцевой придумаешь, то для кольцевой потом тривиально. Если умеешь считать суммы всех элементов от нулевого до i-го(обозначи S(i)), то

сумма элементов от i до j-1 если i<j будет S(j)-S(i).

сумма элементов от i до j-1 если i>j (идем по кругу) будет S(n)-S(i)+S(j).

Короче говоря, смысл таков, что если придумаешь эффективную некольцевую структуру, то и для кольцевой все получится.

Дерево слишком сложно, вычислительно. Значительная часть запросов будет длины 1-3 элемента. Пока откатываюсь к тривиальной реализации. А для длинных запросов сумм надо будет наверно делать заранее рассчитанный массив сумм, с учетом выхода за границы, чтобы избавится от условий и разбиения отрезка на два.

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

ЗЫ можно элементы поместить в k-мерный массив и тогда доступ к единичным будет в k раз дольше, но любая сумма считаться за n^(1/k)+k

KISS

#define nelem(x) (sizeof(x) / sizeof((x)[0]))

int array[100];

int
sum(int from, int to)
{
        int i, n = 0;

        if (to > from)
                return 0;

        for (i = from; i <= to; i++)
                n += array[i % nelem(array)];

        return n;
}

PS: как же я давно C не трогал! ;)

       if (to > from)
                return 0;

Так ведь в этом случае for и так ни разу не выполнится, n=0, и последний return все правильно отработает?

Согласен. Привычка отсеивать corner-cases сыграла злую шутку. Там ещё и переполнение целого, но для демонстрации принципа это не важно.

%

не Ъ операция, Ъ не поймут

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

Что-то не понял, как именно надо надо располагать элементы в двумерном массиве?

Для n элементов заводишь массив m*m, где m=sqrt(n). Располагаешь подряд. То есть сперва заполняешь первую строчку, потом вторую итд. Считаешь суммы в каждой строке. Получается, что если тебе нужна сумма под диапазону, то те строки, которые в этот диапазон входят, уже пересчитывать не надо.

взять boost::ring_buffer (или как его там) отнаследовать, добавив операцию выборки n элементов

А если надо больше одной очереди?

А если to > 100?

А стоп туплю, там же %...

Тем не менее, тебе правильно подсказали про дерево фенвика (так называемое Binary Indexed Tree (BIT)). Можно организовать на нем и получение частичной суммы на интервале. Почему дерево сложно?