如何高效解决带更新操作的跳跃到终点次数查询问题

你的原始DP方案在更新操作时需要重置大量前置状态，导致最坏时间复杂度达到O(NQ)，无法处理1e5规模的数据。下面介绍平方根分块解法，能将时间复杂度优化到O((N+Q)×√N)，完全满足题目约束。

核心思路 #

把数组划分为大小为√N的若干块，每个元素维护两个信息：

• dp[i]：从i出发，跳出当前块所需的跳跃次数
• next[i]：从i出发，跳出当前块后到达的位置

查询时可以快速跳过整个块，避免逐次跳跃；更新时仅需重新计算当前块内的元素，无需修改所有前置状态。

具体实现步骤 #

1. 初始化分块 #

• 计算块大小 B = (int) Math.sqrt(N)
• 从后往前遍历每个元素i：
  • 如果 J[i] >= N：说明跳一次就到终点外，dp[i] = 1，next[i] = N
  • 如果i和J[i]在同一个块内：dp[i] = 1 + dp[J[i]]，next[i] = next[J[i]]
  • 如果不在同一个块内：跳一次就出块，dp[i] = 1，next[i] = J[i]

2. 查询操作 #

从起点s开始累加跳跃次数：

• 初始化结果res = 0
• 当s < N时，累加当前块的跳跃次数res += dp[s]，然后跳到块外的位置s = next[s]
• 最终返回res

3. 更新操作 #

修改指定位置i的J值后，重新计算i所在块内的所有元素：

• 找到i所在块的起始位置start = (i / B) * B
• 从块的末尾（Math.min(start + B - 1, N-1)）往前遍历到start，按初始化的逻辑重新计算每个元素的dp和next值

Java代码实现 #

import java.util.ArrayList;
import java.util.List;

public class JumpGame {
    static int[] J;
    static int[] dp;
    static int[] next;
    static int B;

    static void init(int n) {
        B = (int) Math.sqrt(n);
        dp = new int[n];
        next = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            if (J[i] >= n) {
                dp[i] = 1;
                next[i] = n;
            } else {
                if (i / B == J[i] / B) {
                    dp[i] = 1 + dp[J[i]];
                    next[i] = next[J[i]];
                } else {
                    dp[i] = 1;
                    next[i] = J[i];
                }
            }
        }
    }

    static int query(int s) {
        int res = 0;
        while (s < J.length) {
            res += dp[s];
            s = next[s];
        }
        return res;
    }

    static void update(int idx, int newVal) {
        J[idx] = newVal;
        int start = (idx / B) * B;
        int end = Math.min(start + B - 1, J.length - 1);
        for (int i = end; i >= start; i--) {
            if (J[i] >= J.length) {
                dp[i] = 1;
                next[i] = J.length;
            } else {
                if (i / B == J[i] / B) {
                    dp[i] = 1 + dp[J[i]];
                    next[i] = next[J[i]];
                } else {
                    dp[i] = 1;
                    next[i] = J[i];
                }
            }
        }
    }

    static List<Integer> solve(int n, int[] jumpSquares, int[][] queries) {
        J = jumpSquares;
        init(n);
        List<Integer> answers = new ArrayList<>();
        for (int[] q : queries) {
            if (q.length == 1) {
                answers.add(query(q[0]));
            } else {
                update(q[0], q[1]);
            }
        }
        return answers;
    }
}

复杂度分析 #

• 初始化：O(N)，仅需遍历一次数组
• 查询：每次最多跳过O(√N)个块，每个块操作O(1)，总时间O(√N)
• 更新：每次仅需重新计算一个块的O(√N)个元素，总时间O(√N)

对于N和Q均为1e5的情况，总操作次数约为1e5×300=3e7，完全在Java的时间承受范围内。

内容的提问来源于stack exchange，提问作者user23274861