Приращение первых n элементов списка при условии условия

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

Таким образом, вам не нужно на самом деле перемещаться по списку, чтобы увеличить его, но вы сохраняете только то, что вы выполняли приращения на диапазонах, например, от {0 до 2} и от {0 до 3}. Кроме того, вы можете также сопоставить некоторые операции, так что если несколько операций увеличиваются до одного и того же индекса, вам нужно сохранить только одну запись.

Наихудшей сложностью этого решения является O(q + gx qlogq + n) где g – число операций get, q – количество обновлений, а n – длина списка. Так как мы можем иметь не более n различных концов для интервалов, это сводится к O(q + nlogn + n) = O(q + nlogn) . Наивное решение, использующее обновление для каждого запроса, будет O(q * l ), где l (длина запроса) может быть до размера n, дающего O(q * n) . Поэтому мы можем ожидать, что это решение будет лучше при q > log n .

Пример рабочего python ниже:

 def RangeStructure(object): def __init__(self, l): self.ranges = collections.defaultdict(int) self.l = l def incToPosition(self, k): self.ranges[k] += 1 def get(self): res = self.l sorted_keys = sorted(self.ranges) last = len(sorted_keys) - 1 to_add = 0 while last >= 0: start = 0 if last < 1 else sorted_keys[last - 1] end = sorted_keys[last] to_add += self.ranges[end] for i in range(start, end): res[i] += to_add last -= 1 return res rs = RangeStructure([10, 20, 30, 40, 50, 60]) rs.incToPosition(2) rs.incToPosition(2) rs.incToPosition(3) rs.incToPosition(4) print rs.get() 

И объяснение:

1. после того, как диапазоны операций inc будут содержать (начало, конец, инк) кортежи формы (0, 2, 2), (0, 3, 1), (0, 4, 1); они будут представлены в dict как {2: 2, 3: 1, 4: 1}, так как начало всегда 1 и может быть опущено

2. во время операции get мы гарантируем, что мы будем работать только с одним элементом списка один раз; мы сортируем диапазоны в порядке возрастания их конечной точки и перемещаем их в обратном порядке, обновляя содержащиеся элементы списка и сумму ( to_add ), добавляемую к последующим диапазонам

Это печатает, как и ожидалось:

 [14, 24, 32, 41, 50, 60] 

Ниже приведена операция-агрегация в NumPy:

 initial_array = # whatever your l is, but as a NumPy array increments = numpy.zeros_like(initial_array) ... # every time you want to increment the first n elements if n: increments[n-1] += 1 ... # to apply the increments initial_array += increments[::-1].cumsum()[::-1] 

Это O(ops + len(initial_array)) , где ops – количество операций приращения. Если вы не делаете небольшое количество приращений в очень небольшой части списка, это должно быть намного быстрее. В отличие от наивной реализации, он не позволяет вам извлекать значения элементов до тех пор, пока не будут применены приращения; если вам нужно это сделать, вам может понадобиться решение на основе структуры BST или BST, чтобы отслеживать приращения.

m – количество запросов, n – список для увеличения длины, O (n + m) идея алгоритма:
так как вам нужно только увеличивать от начала до некоторого k-го элемента, вы получите диапазоны приращений. Пусть наше приращение будет парой (с точностью до позиции, приращением на). Пример:
(1, 2) – позиции приращения 0 и 1 на 2
Если мы пытаемся вычислить значение в позиции k, тогда мы должны добавить приращения, которые имеют позиции, большие или равные k, к текущему значению в позиции k. Как мы можем быстро вычислить сумму приращений, у которых есть позиции больше или равные k? Мы можем начать вычислять значения из задней части списка, а затем помнить сумму приращений.
Доказательство концепции:

 # list to increment a = [1, 2, 5, 1, 6] # (up to and including k-th index, increment by value) queries = [(1, 2), (0, 10), (3, 11), (4, 3)] # decribed algorithm implementation increments = [0]*len(a) for position, inc in queries: increments[position] += inc got = list(a) increments_sum = 0 for i in xrange(len(increments) -1, -1, -1): increments_sum += increments[i] got[i] += increments_sum # verify that solution is correct using slow but correct algorithm expected = list(a) for position, inc in queries: for i in xrange(position + 1): expected[i] += inc print 'Expected: ', expected print 'Got: ', got 

вывод:

 Expected: [27, 18, 19, 15, 9] Got: [27, 18, 19, 15, 9] 

Вы можете использовать понимание списка и добавить оставшийся список

 [x + 1 for x in a[:n]]+a[n:]