Binary Lifting for Non-Graph Function Iteration

Why Binary Lifting for Non-Graph Function Iteration Matters

In many algorithmic domains, we encounter a deterministic transition function $f: S \to S$ defined over a finite domain $S$ of size $N$. Given an initial state $x_0 \in S$ and a massive iteration count $K$ (where $K$ can be as large as $10^{18}$), the task is to compute the $K$-th iterated function value $f^K(x_0) = f(f(\dots f(x_0)\dots))$. A naive loop that applies $f$ sequentially $K$ times takes $O(K)$ time, which is computationally impossible when $K = 10^{18}$.

While tree-based binary lifting optimizes parent pointer navigation, Binary Lifting for Non-Graph Function Iteration applies the exact same exponential jump principle to arbitrary discrete functions, array index mappings, next-element pointers, or state machine transitions. By precomputing jump tables jump[x][j] corresponding to $f^{2^j}(x)$ for exponents $j \in [0, \lfloor \log_2 K \rfloor]$, evaluating any $K$-step functional transition reduces to combining at most $\lfloor \log_2 K \rfloor + 1$ functional jumps. This reduces the query time from $O(K)$ to $O(\log K)$ per lookup after an $O(N \log K_{max})$ preprocessing phase, while effortlessly tracking associative path monoids like path sums, minimums, or string hashes.

Core Concepts and Terminology

Understanding non-graph binary lifting requires formalizing functional composition over discrete state domains. Let $S = \{0, 1, \dots, N-1\}$ be a finite state space and $f: S \to S$ be a deterministic mapping.

1. Functional Iteration ($f^k(x)$): The $k$-th recursive application of $f$, defined as $f^0(x) = x$ and $f^k(x) = f(f^{k-1}(x))$.
2. Jump Table (jump[x][j]): A 2D array where jump[x][j] stores $f^{2^j}(x)$.
3. Composition Recurrence: The identity $f^{2^j}(x) = f^{2^{j-1}}\!\left(f^{2^{j-1}}(x)\right)$ enables constructing column $j$ directly from column $j-1$ in $O(N)$ time.
4. Associated Value / Path Monoid (val[x][j]): An optional auxiliary table tracking an associative property (such as the minimum, maximum, or sum of transition costs) over the $2^j$ steps starting at state $x$.

How Binary Lifting for Non-Graph Function Iteration Works, Step by Step

The algorithm operates in two distinct phases: Precomputation and Query Evaluation.

Phase 1: Precomputation ($O(N \log K_{max})$)

1. Determine $\text{LOG} = \lfloor \log_2 K_{max} \rfloor + 1$. Allocate jump[N][LOG] and optional path_sum[N][LOG].
2. Initialize column $j = 0$: jump[x][0] = f[x] and path_sum[x][0] = weight[x] for all $x \in S$.
3. For $j = 1$ up to $\text{LOG} - 1$: For each state $x \in S$: Let $mid = \text{jump}[x][j-1]$. Set $\text{jump}[x][j] = \text{jump}[mid][j-1]$. Set $\text{path\_sum}[x][j] = \text{path\_sum}[x][j-1] + \text{path\_sum}[mid][j-1]$.

Phase 2: Query Evaluation ($O(\log K)$)

To compute $f^K(x)$ and accumulated path weight starting from $x$:

1. Set curr = x and acc = 0.
2. For exponent $j = \text{LOG} - 1$ down to $0$: Check if bit $j$ of $K$ is set ((K >> j) & 1). If set: acc += path_sum[curr][j] curr = jump[curr][j]

1. Return (curr, acc).

The control flow diagram below details the loop and decision structure for non-graph binary lifting:

flowchart TD
A[Start Query: state x, steps K] --> B[Initialize curr = x, acc = 0, j = LOG - 1]
B --> C{j >= 0?}
C -- Yes --> D{Is j-th bit of K set? K & 1<<j}
D -- Yes --> E[acc = acc + path_sum curr j]
E --> F[curr = jump curr j]
D -- No --> G[Decrement j: j = j - 1]
F --> G
G --> C
C -- No --> H[Return final state curr and path sum acc]

Worked Example with a Full Trace

Let us trace an explicit function and query end-to-end.

Domain Size: $N = 6$, States $S = \{0, 1, 2, 3, 4, 5\}$.

Base Function $f$: $f = [2, 3, 4, 1, 0, 2]$.

Transition Weights $w$: $w = [5, 10, 2, 8, 1, 4]$.

We precompute up to $j = 3$ ($2^3 = 8$ steps) and evaluate $f^{11}(0)$.

Precomputed Tables

• jump[x][j] table:
• $j=0$ ($2^0=1$): [2, 3, 4, 1, 0, 2]
• $j=1$ ($2^1=2$): [4, 1, 0, 3, 2, 4]
• $j=2$ ($2^2=4$): [2, 1, 4, 3, 0, 2]
• $j=3$ ($2^3=8$): [4, 1, 0, 3, 2, 4]

• path_sum[x][j] table:
• $j=0$ ($2^0=1$): [5, 10, 2, 8, 1, 4]
• $j=1$ ($2^1=2$): [7, 18, 3, 18, 6, 6]
• $j=2$ ($2^2=4$): [13, 36, 10, 36, 9, 12]
• $j=3$ ($2^3=8$): [23, 72, 19, 72, 22, 22]

Query Trace ($x = 0$, $K = 11 = 8 + 2 + 1 = 1011_2$)

1. Bit $j=3$ ($2^3 = 8$ steps): acc += path_sum[0][3] ($0 + 23 = 23$) curr = jump[0][3] ($0 \to 4$)

1. Bit $j=2$ ($2^2 = 4$ steps): Bit is 0, skip.
2. Bit $j=1$ ($2^1 = 2$ steps): acc += path_sum[4][1] ($23 + 6 = 29$) curr = jump[4][1] ($4 \to 2$)

1. Bit $j=0$ ($2^0 = 1$ step): acc += path_sum[2][0] ($29 + 2 = 31$) curr = jump[2][0] ($2 \to 4$)

Final Answer for $f^{11}(0)$: Final State = 4, Total Path Sum = 31.

Implementation in Python, C++, and Java

The complete, runnable code blocks below demonstrate Non-Graph Binary Lifting with path sum accumulation. All three language implementations execute identical logic, use the exact same sample dataset, and print identical output.

class BinaryLiftingFunction:
    def __init__(self, f, weights, max_k):
        self.n = len(f)
        self.LOG = max_k.bit_length()
        if self.LOG == 0:
            self.LOG = 1

        self.jump = [[0] * self.LOG for _ in range(self.n)]
        self.path_sum = [[0] * self.LOG for _ in range(self.n)]

        # Initialize base column (j = 0, 2^0 = 1 step)
        for i in range(self.n):
            self.jump[i][0] = f[i]
            self.path_sum[i][0] = weights[i]

        # Build power-of-two jump tables
        for j in range(1, self.LOG):
            for i in range(self.n):
                mid = self.jump[i][j - 1]
                self.jump[i][j] = self.jump[mid][j - 1]
                self.path_sum[i][j] = self.path_sum[i][j - 1] + self.path_sum[mid][j - 1]

    def query(self, start_state, k):
        curr = start_state
        total_sum = 0
        for j in range(self.LOG - 1, -1, -1):
            if (k >> j) & 1:
                total_sum += self.path_sum[curr][j]
                curr = self.jump[curr][j]
        return curr, total_sum


if __name__ == "__main__":
    f = [2, 3, 4, 1, 0, 2]
    weights = [5, 10, 2, 8, 1, 4]
    max_k = 100

    bl = BinaryLiftingFunction(f, weights, max_k)

    queries = [(0, 11), (1, 13), (3, 7)]
    for idx, (x, k) in enumerate(queries, 1):
        end_state, sum_val = bl.query(x, k)
        print(f"Query {idx} (start={x}, K={k}): Final State = {end_state}, Path Sum = {sum_val}")

#include <iostream>
#include <vector>
#include <utility>

class BinaryLiftingFunction {
private:
    int n;
    int LOG;
    std::vector<std::vector<int>> jump;
    std::vector<std::vector<long long>> path_sum;

public:
    BinaryLiftingFunction(const std::vector<int>& f, const std::vector<long long>& weights, long long max_k) {
        n = static_cast<int>(f.size());
        LOG = 0;
        while ((1LL << LOG) <= max_k) {
            LOG++;
        }
        if (LOG == 0) LOG = 1;

        jump.assign(n, std::vector<int>(LOG, 0));
        path_sum.assign(n, std::vector<long long>(LOG, 0));

        // Initialize base column (j = 0, 2^0 = 1 step)
        for (int i = 0; i < n; ++i) {
            jump[i][0] = f[i];
            path_sum[i][0] = weights[i];
        }

        // Build power-of-two jump tables
        for (int j = 1; j < LOG; ++j) {
            for (int i = 0; i < n; ++i) {
                int mid = jump[i][j - 1];
                jump[i][j] = jump[mid][j - 1];
                path_sum[i][j] = path_sum[i][j - 1] + path_sum[mid][j - 1];
            }
        }
    }

    std::pair<int, long long> query(int start_state, long long k) const {
        int curr = start_state;
        long long total_sum = 0;
        for (int j = LOG - 1; j >= 0; --j) {
            if ((k >> j) & 1LL) {
                total_sum += path_sum[curr][j];
                curr = jump[curr][j];
            }
        }
        return {curr, total_sum};
    }
};

int main() {
    std::vector<int> f = {2, 3, 4, 1, 0, 2};
    std::vector<long long> weights = {5, 10, 2, 8, 1, 4};
    long long max_k = 100;

    BinaryLiftingFunction bl(f, weights, max_k);

    std::vector<std::pair<int, long long>> queries = {{0, 11}, {1, 13}, {3, 7}};
    for (size_t i = 0; i < queries.size(); ++i) {
        auto res = bl.query(queries[i].first, queries[i].second);
        std::cout << "Query " << (i + 1) << " (start=" << queries[i].first
                  << ", K=" << queries[i].second << "): Final State = "
                  << res.first << ", Path Sum = " << res.second << "\n";
    }

    return 0;
}

public class Main {

    public static class BinaryLiftingFunction {
        private final int n;
        private final int LOG;
        private final int[][] jump;
        private final long[][] pathSum;

        public BinaryLiftingFunction(int[] f, long[] weights, long maxK) {
            this.n = f.length;
            int logCount = 0;
            while ((1L << logCount) <= maxK) {
                logCount++;
            }
            this.LOG = Math.max(1, logCount);

            this.jump = new int[n][LOG];
            this.pathSum = new long[n][LOG];

            // Initialize base column (j = 0, 2^0 = 1 step)
            for (int i = 0; i < n; i++) {
                jump[i][0] = f[i];
                pathSum[i][0] = weights[i];
            }

            // Build power-of-two jump tables
            for (int j = 1; j < LOG; j++) {
                for (int i = 0; i < n; i++) {
                    int mid = jump[i][j - 1];
                    jump[i][j] = jump[mid][j - 1];
                    pathSum[i][j] = pathSum[i][j - 1] + pathSum[mid][j - 1];
                }
            }
        }

        public long[] query(int startState, long k) {
            int curr = startState;
            long totalSum = 0;
            for (int j = LOG - 1; j >= 0; j--) {
                if (((k >> j) & 1L) == 1L) {
                    totalSum += pathSum[curr][j];
                    curr = jump[curr][j];
                }
            }
            return new long[]{curr, totalSum};
        }
    }

    public static void main(String[] args) {
        int[] f = {2, 3, 4, 1, 0, 2};
        long[] weights = {5, 10, 2, 8, 1, 4};
        long maxK = 100;

        BinaryLiftingFunction bl = new BinaryLiftingFunction(f, weights, maxK);

        long[][] queries = {{0, 11}, {1, 13}, {3, 7}};
        for (int i = 0; i < queries.length; i++) {
            int start = (int) queries[i][0];
            long k = queries[i][1];
            long[] res = bl.query(start, k);
            System.out.println("Query " + (i + 1) + " (start=" + start + ", K=" + k +
                    "): Final State = " + res[0] + ", Path Sum = " + res[1]);
        }
    }
}

Complexity, Correctness, and Invariants

The formal justification for Non-Graph Binary Lifting relies on the associativity of functional composition and the uniqueness of binary number representation.

Variants, Pitfalls, and Optimizations

Common Variants

1. Binary Lifting over Monoids (Path Min / Max / GCD / Hash):

When each state transition $x \to f(x)$ carries an associative value, path aggregates are precomputed alongside jump pointers: val[x][j] = val[x][j-1] ⊕ val[jump[x][j-1]][j-1], where $\oplus$ is any associative operator. 2. Double Binary Lifting (Binary Search on Step Count): Used to find the minimum steps $K$ required to satisfy a target condition (such as path sum $\ge T$). By trying exponents $j = \text{LOG}-1$ down to $0$, if taking a $2^j$-step jump keeps the total path value below $T$, the search jumps $2^j$ steps and adds $2^j$ to $K$. 3. Partial Function Handling (Terminal States): If $f(x)$ is a partial mapping where some states have no outgoing transition, set terminal states to self-loops ($f(x) = x$) with identity transition weight ($0$ for sum, $\infty$ for min) to prevent pointer errors during binary lifting.

Practice Problems and Real-World Use

Binary lifting for non-graph function iteration is a core technique across competitive programming, string processing, state machine fast-forwarding, and distributed lookup systems.