algorithm - 使用矩阵在 O(1) 时间内回答查询

Question

这是作业，我已经有了答案。我只是想了解它的样子，因为我无法想象它。

Suppose that we are given a sequence of n values x1, x2, ..., xn and seek to quickly answer repeated queries of the form: given i and j, find the smallest value in xi, . . . , xj .

问题是:

a) Design a data structure that uses O(n^2) space and answers queries in O(1) time.

根据 Skienna 的维基页面，答案是

Use an nxn matrix populated with the distance between the nodes at the two indices.

我知道 n x n 矩阵会给我们 n^2 空间，但我不明白这个矩阵是什么样的。

Answer 1

嗯...让我们举个例子:

对于值:3 5 4 2

矩阵将是:

3 3 3 2
3 5 4 2
3 4 4 2
2 2 2 2

矩阵总是symmetric :我们可以允许 j < i表示 x_j..x_i

这称为查找表。 (i, j) 处的每个值都等于 min(x_i..x_j)。这意味着，您预先计算您的正常函数将返回的值。