<p>如果要多次更新一个大列表的大范围,请使用更合适的数据结构,这样每次更新都不会花费O(<em>n</em>)。你知道吗</p>
<p>一种这样的数据结构是<a href="https://cp-algorithms.com/data_structures/segment_tree.html#toc-tgt-9" rel="nofollow noreferrer">segment tree</a>,其中每个列表元素对应于树中的叶节点;列表元素的真值可以表示为叶节点和根节点之间的路径上的值的总和。这样,将一个数字添加到单个内部节点实际上就像将它添加到该子树表示的所有列表元素一样。你知道吗</p>
<p>数据结构支持在O(log<em>n</em>)时间内按索引执行get/set操作,也支持在O(log<em>n</em>)时间内执行add-in-range操作。下面的解决方案使用二叉树,使用长度为<;=2n的列表实现</p>
<pre class="lang-py prettyprint-override"><code>class RangeAddList:
def __init__(self, vals):
# list length
self._n = len(vals)
# smallest power of 2 >= list length
self._m = 1 << (self._n - 1).bit_length()
# list representing binary tree; leaf nodes offset by _m
self._vals = [0]*self._m + vals
def __repr__(self):
return '{}({!r})'.format(self.__class__.__name__, list(self))
def __len__(self):
return self._n
def __iter__(self):
for i in range(self._n):
yield self[i]
def __getitem__(self, i):
if i not in range(self._n):
raise IndexError()
# add up values from leaf to root node
t = 0
i += self._m
while i > 0:
t += self._vals[i]
i >>= 1
return t + self._vals[0]
def __setitem__(self, i, x):
# add difference (new value - old value)
self._vals[self._m + i] += x - self[i]
def add_in_range(self, i, j, x):
if i not in range(self._n + 1) or j not in range(self._n + 1):
raise IndexError()
# add at internal nodes spanning range(i, j)
i += self._m
j += self._m
while i < j:
if i & 1:
self._vals[i] += x
i += 1
if j & 1:
j -= 1
self._vals[j] += x
i >>= 1
j >>= 1
</code></pre>
<p>示例:</p>
<pre class="lang-py prettyprint-override"><code>>>> r = RangeAddList([0] * 10)
>>> r.add_in_range(0, 4, 10)
>>> r.add_in_range(6, 9, 20)
>>> r.add_in_range(3, 7, 100)
>>> r
RangeAddList([10, 10, 10, 110, 100, 100, 120, 20, 20, 0])
</code></pre>
<p>事实证明,NumPy优化得非常好,在段树跟上之前,您需要向上搜索长度为50000左右的列表。对于我的机器上长度为100000的列表,段树的更新速度仍然只有NumPy的O(<em>n</em>)范围更新速度的两倍。您可能希望使用自己的数据进行基准测试。你知道吗</p>