1️⃣0️⃣9️⃣ What is Prefix Sum?

Answer:

Prefix Sum is a technique where each element stores the cumulative sum of all previous elements, allowing fast range sum queries.

Formula:

Prefix[i] = Prefix[i-1] + Array[i]

Applications:

• Range sum queries

• Subarray problems

• Competitive programming

Benefit: Range sums can be calculated in O(1) after preprocessing.

1️⃣1️⃣0️⃣ What is Binary Lifting?

Answer:

Binary Lifting is an advanced algorithm used to efficiently answer ancestor-related queries in trees by precomputing ancestors at powers of two.

Applications:

• Lowest Common Ancestor (LCA)

• Tree Queries

• Competitive Programming

Time Complexity:

• Preprocessing: O(n log n)

• Query: O(log n)

Double Tap ❤️ For Part-12