f[i][j] 表示从节点i跳2^j步到的节点坐标

若要从0点跳到7:

5B55CC14-CB16-407D-BD21-AA99BBADA57B.png

  1. f[0][3] = 8 > 7，不能跳 2^3 步
  2. f[0][2] = 4 < 7，可以先跳 2^2 步到 4
  3. f[4][3] = 12 > 7，不能跳 2^3 步
  4. f[4][2] = 8 > 7，不能跳 2^2 步
  5. f[4][1] = 6 < 7，可以跳到 2^1 步到 6
  6. 。。。
  7. f[6][0] = 7 跳1步到7

RMQ（Range Maximum Query）区域最值查询算法

f[i][j] 表示从节点i到之后的2^j步内区域的最大值

Sparse Table 算法

3CDC70D0-6508-4647-B481-4681CF25E9BD.png

570987D7-C2E0-4FE4-920B-74ABFCFBD3DC.png

注：log2 在java中可以是：Math.log(m) / Math.log(2)