在给定条件的情况下增加前n个列表元素
例如，我有一个列表
l = [10, 20, 30, 40, 50, 60]
我需要增加列表中前n元素的条件。 条件与列表无关。 例如，如果n = 3 ，则列表l应该变为：
l = [11, 21, 31, 40, 50, 60]
我知道我可以在列表的每个元素上使用for循环。 但我需要做大约1.5亿次这样的操作。 所以，我正在寻找一个更快的方法来做到这一点。 任何帮助，高度赞赏。 提前致谢
您可以在列表顶部创建一个简单的数据结构，该结构存储每个增量操作的开始和结束范围。 在你的情况下，开始将是0，所以你可以只存储结束。
这样，您不必实际遍历列表来增加元素，但您只能保留在范围内执行增量，例如{0到2}和{0到3}。 此外，还可以整理一些操作，以便如果多个操作增加到相同的索引，则只需存储一个条目。
此解决方案的最坏情况复杂度为O(q + gx qlogq + n)其中g是获取操作的数量，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()
并做出解释：
在inc操作范围中将包含（0,2,2），（0,3,1），（0,4,1）;（0,1,2）等形式的（start，end，inc）元组。 这些将在字典中表示为{2：2,3：1,4：1}，因为开始始终为1并且可以省略
在get操作期间，我们确保我们只对任何列表元素进行操作; 我们按照其终点的to_add对范围进行排序，并以相反的顺序遍历它们，以更新包含的列表元素和总和（ 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]