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 です)
何が欠けていますか？誰でも説明できますか？