algorithm - 如何提高这个算法的时间复杂度？

Question

• n名单规模
• v[n]所有值都设置为 0 的列表
• update(k, a)设置v[k] += a的操作
• query(a, b)返回 v[a] + v[a+1] + ... + v[a+b] 之和的操作, a<b

这些操作使算法的时间复杂度为 O(n * cost of one operation) :

---------------------------
| update | query | total  |
---------------------------
|  O(1)  |  O(n) |  O(n)  |
---------------------------

是否有任何版本的update和 query将提高总时间复杂度的操作？

例如，我尝试缓存 0 之间的所有金额和 n在update操作，但我得到了一个更慢的算法:

---------------------------
| update | query | total  |
---------------------------
| O(n^2) |  O(1) | O(n^2) |
---------------------------

有什么建议吗？

我感兴趣的是最坏的情况。

我已经知道两个版本:每个版本都有一个操作 O(1)和另一个O(n)或更高。

Answer 1

正如 Niklas 所说，这个问题或多或少是 Fenwick trees专为(您的查询可以作为两个前缀和的差来回答)。我写这个答案是为了指出可以以不同的方式权衡运营成本。

首先，您的具有廉价查询的算法可以将其更新时间改进为 O(n):提前仅计算前缀和并使用上述差分技巧。而且，我们可以提取主要思想并将其应用于任何支持操作的数据结构

update(k, a, b): for i in a..b, do s[i] += k
query(i): return s[i],

s 现在保存前缀和而不是实际值。

现在，经典的 Fenwick/线段树每个内部节点有 d = 2 个子节点(二元的)。没有什么可以阻止我们选择 d 的其他值。 update 或 query 必须访问节点及其祖先，而另一个必须访问包含输入区间的段。前一种访问方式需要时间 O(log n/log d)。后一种模式需要时间 O(d (log n/log d))。在此框架中，您提出的算法本质上采用 d = n。通过采用 d 的其他值，我们可以考虑查询/更新操作的精确组合以及可能有利于更扁平树结构的架构细节。