python - 如何降低程序的时间复杂度？

Question

我正在解决以下问题: 有一排编号为 1 到 n 的桶。一位园丁以一种特殊的方式装满这个水桶。他用 1<=l<=r<=n 填充两端 l 和 r 之间的桶，包括 l 和 r。他这样做了 k 次。我们需要找到桶中的水等于桶中体积的中位数。我正在使用时间复杂度 knlgn 的程序来解决这个问题。输入是这样的:第一行包含由空格分隔的 n 和 k，接下来的 k 行包含每个浇水过程的 l 和 r 对。我正在使用 nklgn 算法来解决这个问题，如下所示:

while True:
nk = input().split(' ')
n = int(nk[0])
k = int(nk[1])
a = input().split(' ')
for z in range(len(a)):
    a[z] = int(a[z])
if n==0 and k==0: break

for mn in range(k):
    (x, y) = input().split(' ')
    x = int(x)-1
    y = int(y)-1
    for z in range(x, y+1):
        a[z] += 1
    print(sorted(a)[int(len(a)/2)])

请帮助我使用更好的算法解决这个问题，我至少遇到过 3 到 4 次非常相似的问题。如果不是完整的代码，您可以在答案中给我一些提示。

Answer 1

我认为你应该使用 Segment Tree .此数据结构用于在 O(log(n)) 时间内更新和检索特定查询。

您可以通过以下方式更新树:首先找到覆盖范围 [l, r] 的节点，然后将更新后的值存储在这些节点中。像这样处理所有查询 - 仅将更新后的值存储在顶级节点中，而不更改原始节点。此后，在预序遍历中，您可以在 O(n) 时间内更新所有必要的节点。我认为这将是一个非常合理的优化。

如果你不知道这个数据结构，那么我建议你先阅读它，然后尝试理解我的回答。