Sparse Table (ST) is a data structure for answering range queries on static arrays. It differs from standard dynamic programming approaches by storing information only for intervals with lengths that are powers of two.

Standard interval DP might define a state dp[l][r] representing data for the interval (l, r). In contrast, the ST table is defined as ST[l][p], representing the data for the interval starting at index l with length 2^p (spanning [l, l + 2^p - 1]). The 'S' stands for sparse, indicating it stores a subset of all possible intervals.

Application in Jump Distance Problems

A classic use case involves an array of n points where each point i can jump forward a distance jump[i]. A monotonicity condition must hold: if i < j, then jump[i] <= jump[j]. This implies no interval defined by a jump completely contains another, allowing the use of the Sparse Table. The goal is to compute the minimum number of jumps between any two points (l, r).

The recurrence relation for building the table is: ST[i][j] = ST[ ST[i][j-1] ][j-1]

After constructing the table, query are processed by binary lifting: start from position l and greedily apply the largest possible jump 2^step that does not exceed the target r. Step length decreases exponentially to approach the destination.

const int MAX_N = 100000;
const int MAX_LOG = 17;
int jumpDist[MAX_N];
int sparseTable[MAX_N][MAX_LOG];
int n; // Number of points
int maxLog;

void buildSparseTable() {
    maxLog = log2(n) + 1;
    for (int i = 0; i < n; ++i) {
        sparseTable[i][0] = i + jumpDist[i];
    }
    for (int j = 1; j <= maxLog; ++j) {
        for (int i = 0; i < n; ++i) {
            int nextPos = sparseTable[i][j-1];
            if (nextPos < n) {
                sparseTable[i][j] = sparseTable[nextPos][j-1];
            } else {
                sparseTable[i][j] = n; // Out of bounds
            }
        }
    }
}

int minJumps(int start, int end) {
    int currentPos = start;
    int jumpCount = 0;
    if (start >= end) return 0;
    for (int k = maxLog; k >= 0; --k) {
        int nextReach = sparseTable[currentPos][k];
        if (nextReach < end) {
            currentPos = nextReach;
            jumpCount += (1 << k);
        }
    }
    // One final jump is needed to reach or pass 'end'
    return jumpCount + 1;
}

Range Queries for Idempotent Functions

The Sparse Table excels at answering range queries for idempotent or overlap-friendly functions. These are opeartions where the answer for an interval can be derived from the enswers of two overlapping subintervals without loss of information. Examples include maximum, minimum, greatest common divisor (GCD), bitwise AND, and bitwise OR.

For example, to query the maximum value in a range [l, r]:

int arr[MAX_N];
int stMax[MAX_N][MAX_LOG];

void buildMaxTable() {
    for (int i = 0; i < n; ++i) {
        stMax[i][0] = arr[i];
    }
    int logVal = log2(n) + 1;
    for (int j = 1; j <= logVal; ++j) {
        for (int i = 0; i + (1 << j) <= n; ++i) {
            int halfStep = 1 << (j-1);
            stMax[i][j] = std::max(stMax[i][j-1], stMax[i + halfStep][j-1]);
        }
    }
}

int queryMax(int left, int right) {
    int intervalLen = right - left + 1;
    int k = log2(intervalLen);
    return std::max(stMax[left][k], stMax[right - (1 << k) + 1][k]);
}