Imagine being asked multiple times: “What’s the sum from index L to R?” If you loop every time, your solution becomes slow. But what if you could answer every query in O(1)? That’s exactly what Prefix Sum does. What is Prefix Sum? Prefix sum stores cumulative sums. Each index stores sum from 0 to i int[] arr = {3, 1, 4, 2}; int[] prefix = new int[arr.length]; prefix[0] = arr[0]; for (int i = 1; i < arr.length; i++) { prefix[i] = prefix[i-1] + arr[i]; } Result: prefix = [3, 4, 8, 10] Why Prefix Sum is Powerful Without prefix sum: Each query → O(n) With prefix sum: Preprocessing → O(n) Each query → O(1) Range Sum Formula Use this: S(L,R)=prefix[R]−prefix[L−1] Special case: If L = 0 → just prefix[R] Implementation public static int rangeSum(int[] prefix, int L, int R) { if (L == 0) return prefix[R]; return prefix[R] - prefix[L-1]; } The Real Insight Do work once → reuse many times Instead of solving each query separately, you precompute smartly.…