我正在查看Range minimum queries。
维基百科说:
长度为 n 的数组有 Θ(n²) 可能的查询。
我不明白这个。这是一个大小为 5 的数组的示例
。可以进行以下查询:
1 个查询 [0,4]
2 个查询 [0,3] 和 [1,4]
3 个查询 [0,2],[1,3] 和 [2,4]
4 个查询 [0,1],[1, 2]、[2,3] 和 [3,4]
5 个查询 [0]、[1]、[2]、[3] 和 [4]
可能的查询总数
[0,4] +
[0,3] + [1,4] +
[0,2] + [1,3] + [2,4] +
[0,1] +[1,2] + [2 ,3] + [3,4] +
[0] + [1] + [2] + [3] + [4]
---------------------------------
15 个查询
但我期待N^2 = 25
查询(其中 N 是数组大小 = 5)
我错过了什么?谁能解释一下?