We are given N squares number 0 to N – 1. Each square has target jump square J[i] (which must be at a larger index). At square i, you can only jump to square J[i]. If J[i] is past the last square, then you are done.

We know all J[i] at the start, then we have Q queries. if query is update, it changes J[i] for a specific i (still satisfies J[i] > i). other type of query ask for how many jumps it takes starting from a given square to go past the last square (N-1).

Constraints:
1 <= N, Q <= 100,000
i + 1 <= J[i] <= 1,000,000

Example:
Jump squares: 
[1, 3, 3, 5]
Get answer fro square 1: 1 -> 3 -> 5 [past end] (2 jumps)
Update square 2's jump square (J[2]) to 4
Get answer for square 2: 2->4 [past end] (1 jump)

I tried to use dp (dynamic programming) to store min jumps from each square, but updates make my solution slow down too much since I have to update dp answer for possibly all the squares.

static int[] dp;

static int getjump(int square, int[] jumpSquares) {
    if (square >= dp.length) return 0; // past end
    if (dp[square] != -1) return dp[square]; // already calc
    return dp[square] = 1 + getjump(jumpSquares[square], jumpSquares); // do one jump and check
}

static List<Integer> solve(int n, int[] jumpSquares, int[][] queries) {
    dp = new int[n];
    for (int i = 0; i < n; i++) dp[i] = -1;
    List<Integer> answers = new ArrayList<Integer>();
    for (int[] qq : queries) {
        if (qq.length == 1) {
             answers.add(getjump(qq[0], jumpSquares));
        } else { // update
             jumpSquares[qq[0]] = qq[1];
             for (int i = 0; i <= qq[0]; i++) dp[i] = -1; 
             // reset answers that might depend on updated square (qq[0])
        }
    }
    return answers;
}

how do I solve this more efficiently (better than O(N*Q))?