I. In-Class Exercises

Programming Exercises

1. Binary Lifting Search Problem 1: L3151
2. Binary Lifting Search Problem 2: L3152

II. Knowledge Summary

✨ Core Idea

The core idea of binary lifting is to double the problem size each time. By making jumps in powers of 2, binary lifting can optimize operations that would otherwise require linear time down to logarithmic time complexity, significantly improving algorithm efficiency.

✨ Application Scenarios

Binary lifting is typically used to solve the following types of problems:

• Query problems: For problems such as Lowest Common Ancestor (LCA) queries and range maximum/minimum queries, binary lifting can quickly skip over large numbers of elements to achieve fast querying.
• Distance and path problems: In graph path queries, such as finding the shortest path from one node to any other node, binary lifting can preprocess each node's "jump" information (e.g., the node reached after jumping 1, 2, 4, ... 2^k steps) to quickly compute the shortest path or minimum cost between any two nodes.
• String and array processing: In string matching or array query problems, binary lifting can be used to build efficient data structures such as suffix arrays and Longest Common Prefix (LCP) arrays.

✨ Algorithm Principle

The basic problem-solving approach of binary lifting is: try jumps in powers of 2 from large to small, progressively approaching the target. Specifically, first try the largest step size (e.g., 2^k). If the jump exceeds the range or does not satisfy the condition, try a smaller step size (2^(k-1)), and so on, until the exact answer is found. This approach is similar to the idea of binary search but is more flexible and applicable to a wider range of scenarios.

✨ Execution Example

Using "find the first position greater than or equal to target in a sorted array" as an example to demonstrate the execution process of binary lifting.

Array a[] = {1, 3, 5, 7, 9, 11, 15, 20, 25, 30, 35, 40, 50, 60, 70, 80} (16 elements), target = 22.

Phase 1: Binary lifting to determine the range

Starting from position 0, double the step size each time to find an interval containing the answer:

Step	Current pos	Step size	Jump to pos+step	a[pos+step]	Compare with target	Action
1	0	1	1	a[1]=3	3 < 22	Jump, pos=1
2	1	2	3	a[3]=7	7 < 22	Jump, pos=3
3	3	4	7	a[7]=20	20 < 22	Jump, pos=7
4	7	8	15	a[15]=80	80 >= 22	Don't jump, range determined as [7, 15]

Phase 2: Try jumps from large to small

Now starting from pos=7, step size starts at 4 and halves each time:

Step	Current pos	Step size	Jump to	a[jump to]	Compare with target	Action
1	7	4	11	a[11]=40	40 >= 22	Don't jump
2	7	2	9	a[9]=30	30 >= 22	Don't jump
3	7	1	8	a[8]=25	25 >= 22	Don't jump

Final pos=7, a[7]=20 < 22, so the first position >= 22 is pos+1 = 8, a[8]=25.

The entire process required only 7 comparisons, far fewer than the 9 needed by linear search.

✨ Detailed Problem-Solving Steps

When using binary lifting to solve problems:

1. Determine the starting point: Usually start from position 0 or some initial state.
2. Binary lifting expansion: Jump with step sizes of 1, 2, 4, 8, 16, ... until the jump no longer satisfies the condition or exceeds the range. This determines the approximate interval containing the answer.
3. Precise positioning from large to small: Starting from the maximum feasible step size determined in the previous step, try progressively smaller step sizes. Jump if the condition is satisfied after jumping; don't jump if it isn't.
4. Obtain the final answer: After all step sizes have been tried, the current position is the answer.

Difference between binary lifting and binary search:

• Binary search requires knowing the search range (left and right) in advance, suitable for scenarios with known boundaries.
• Binary lifting does not require knowing the range in advance; it automatically determines the range in the first phase, suitable for scenarios where the range is unknown or extremely large.

✨ Common Mistakes

• Out of bounds when doubling the step size: During the lifting phase, the step size grows very fast. You must check whether pos + step exceeds the array bounds; otherwise, an array out-of-bounds error will occur.
• Forgetting the second phase of precise positioning: Only doing the lifting expansion without the large-to-small precise search gives only a rough range, not an exact answer.
• Incorrect initial step size or halving method: The step size in the second phase should start from the last successfully jumped step size in the lifting phase, halving each time until the step size is 0.
• Confusing with binary search: Both binary lifting and binary search can complete a search in O(log n), but the implementations differ. When the range is known, the two methods are equivalent; when the range is unknown, binary lifting is more convenient.

III. Homework

Programming Exercises

1. Find the Closest Element: L3153