Code : Binary Lifting

#include <bits/stdc++.h>

using namespace std;

const int lg = 21;

class BinaryLifting {
  public:
    int n;
    vector<int> a;
    vector<vector<int>> jump;
    BinaryLifting(int n) {
        this->n = n;
        a.resize(n);
        jump.resize(n, vector<int>(lg, -1));
    }

    void prepare_lifts() {
        // jump[i][j] is the node that you would reach if you take 2^j
        // steps starting from node i.
        for (int i = 0; i < n - 1; i++) {
            jump[i][0] = i + 1;
        }

        // Caution : Loop Order.
        // You should iterate powers of 2 first.
        for (int j = 1; j < lg; j++) {
            for (int i = 0; i < n; i++) {
                // Make the first half of the jump.
                int mid = jump[i][j - 1];
                if (mid == -1) {
                    continue;
                }
                // Make the second half of the jump.
                jump[i][j] = jump[mid][j - 1];
            }
        }
    }

    vector<int> split(int num) {
        vector<int> res;
        for (int i = 0; i < lg; i++) {
            if ((1 << i) & num) {
                res.push_back(i);
            }
        }
        return res;
    }

    int walk(int src, int steps) {
        vector<int> powers_of_2 = split(steps);

        int now = src;
        for (int p : powers_of_2) {
            now = jump[now][p];
            if (now == -1) {
                break;
            }
        }
        return now;
    }
};

void solve() {
    int n = 1e5;
    BinaryLifting blift(n);
    blift.prepare_lifts();
}

int main(int argc, char **argv) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}