Что такое хорошая структура данных для сохранения кумулятивных значений?

Я ищу идею, концепцию или доказанную структуру данных, которая была бы очень эффективной при обращении к коллекции, которая сохраняет кумулятивные значения.

Пример может пролить свет на мою потребность:

У меня есть список значений (2,3,5). Этот список при просмотре кумулятивных значений будет (2,5,10).

Теперь я добавлю 1 в начале списка и получаю (1,2,3,5) и в кумулятивных терминах (1,3,6,11).

Мне нужно только посмотреть на кумулятивные значения, меня совсем не интересует 1,2,3,5. Мне нужно иметь возможность быстро вставлять в позицию, удалять позицию, и все это должно быстро обновлять кумулятивный массив (в идеале без итерации по всему массиву и пересчета значений).

Любые идеи или подсказки?

@Kristo (слишком долго, чтобы добавить комментарий): Чтобы выяснить, почему отрицательные числа делают бессмысленным значение общей суммы, пожалуйста, следуйте этому примеру.

Вставить 1, а затем -1. Сумма составляет 1, чем 0. (1, -1)//(1,0) Вставьте 3, а затем вставьте -3. Сумма равна 3, затем 0. (1,3, -1, -3)//(1,4,3,0) Вставьте 2, а затем вставьте -2. Сумма равна 2, затем 0. (1,3,2, -1, -2, -3)//(1,4,6,5,3,0)

Если мое "магическое число" было 4 общей суммы, я бы не сказал, превысил ли я его.

PS: Основная причина этого - уметь определить, переместил ли я определенное значение и где в цепочке.

Ответ 1

Единственная оптимизация, о которой я могу думать, - это "ленивая" оценка кумулятивного списка.

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

idx  values       cumulative    operation
 3   (2,3,5)      (2, 5, 10)
 0   (1,2,3,5)    (X,X,X,X)     insert 1 at 0 
 3   (1,2,3,5)    (1,3,6,X)     look for value over 5     
 3   (1,2,3,5,4)  (1,3,6,X,X)   insert 4 at 4

Если курс, это не принесет вам много пользы, если вы обычно добавляете элементы в начале списка.

Ответ 2

Используйте двоичное дерево поиска с дополнительным свойством, в котором узлы содержат сумму своего поддерева. Все операции по-прежнему равны O (lg n). Чтобы вставить или удалить значение, вы выполняете обычную процедуру, а также обновляете суммы всех родителей. Получение суммы так же просто, как найти node, содержащий элемент, и вернуть его сумму минус ее правую дочернюю сумму.

Ответ 3

Проверьте совокупную таблицу частот.

Ответ 4

В С# я бы сохранил все фактические значения в списке и использовал пользовательский итератор для циклических вычислений.

Вы пересчитываете только до того момента, когда итератор сообщает вам, что вы прошли свой предел (очевидно, вам нужно будет это кодировать).

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

Ответ 5

Есть два простых способа, которые я вижу: оба используют базовые типы данных - списки.

Сохраните исходный список и пересчитайте кумулятивы при каждом изменении.
Сохраняйте только кумулятивный список и добавляйте его или удаляйте с помощью следующих функций:
- Добавить (элемент, позиция по умолчанию - конец списка) добавит значение элемента, начинающегося с позиции-1.
- Удалить (позиция) будет вычислять исходное значение, вычитая два числа, а затем уменьшает это число из остальной части списка перед удалением элемента.
Добавить 2: (2) добавляет 2 в пустой список.

Добавить 3: (2,5) добавляет 3 в конце списка к предыдущему элементу (2).

Добавить 5: (2,5,10) добавляет 5 в конце списка к предыдущему элементу (5).

Добавить 1 в начале: (1,3,6,11) добавляет 1 в начале списка и увеличивается на 1 до конца (без предшествующих элементов).

Добавить 7 на 2-й позиции: (1,8,11,14,19) добавляет 7 и увеличивается на 7 до конца (без предшествующих элементов).

Удалить третью позицию (11): (1,8,3,8) получить значение, удалить его, добавить значение в остальное.

Этот способ сохранит все синхронизацию, не сохраняя исходные значения.

Ответ 6

Используя термины С++, вы можете уйти с помощью std::list (простые вставки/удаления в середине) или std::set (всегда отсортированные) для данных и одна переменная для хранения суммы? На каждой вставке/удалении вы изменяете сумму по мере необходимости. Сумма представляет наибольшее число в вашем потенциальном кумулятивном списке. Только когда вы нарушите свое магическое число, вам нужно выполнить некоторую алгоритмическую работу, чтобы выяснить, где вы столкнулись.

Update:

Основываясь на вашей новой информации, я не вижу много доступных ярлыков. Вам нужно часто вставлять или удалять их из середины, чтобы предлагать какой-то подход с привязанным списком. Вы можете немного сэкономить расчет, только обновив части списка, которые изменились. Пусть L - список значений, а n - желаемое место в списке. Вставить значение x в местоположение n:

Вставьте значение x + L(n-1) в папку n
Добавьте x ко всем элементам после этого нового n
Остановитесь, если вы нарушите свой магический номер

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

Ответ 7

Вы можете посмотреть структуру данных для совокупной частоты Двоичные индексированные деревья

Вы можете разбить свой диапазон значений на фиксированные диапазоны бит. Ex. 3 интервала:

#define NUM (1<<24)  // max value in your data set
#define BITS0 8
#define BITS1 8
int cum0[NUM >> (BITS0+BITS1)]; // sum of cum1
int cum1[NUM >> BITS1]; // sum of count
int count[NUM];

int add(id, val) { // add a value
  cum0[id >> (BITS0+BITS1)] += val;
  cum1[id >> BITS1] += val; 
  count[id] += val;                     
}

int cumvalue(int id) { int cum = 0; // return cum value at index id         
  for(i = 0; i < (id >> (BITS0+BITS1));i++) cum += cum0[i]; i <<= BITS0;
  for(i = (id & ~((1 << (BITS0+BITS1))-1)) >> BITS1; i < (id >> BITS1); i++) cum+= cum1[i]; i <<= BITS1;
  for(i = id & ~((1 << BITS1) -1); i < id; i++) cum += count[i];            
  return cum;
}