Method Explanation

Abstract: The problem asks us to find the optimal index to minimize a specific cost function involving array elements and prefix sums. By analyzing the transition from index $i$ to $i+1$, we can observe that the required values change dynamically in ranges.

Instead of recomputing the value for each starting position from scratch (which takes $O(N^2)$ time), we can maintain the candidate values using a Segment Tree with Lazy Propagation.

1. Initialization: We initialize the Segment Tree where each leaf $l$ stores the initial value derived from $A[l]$ and the prefix sums of $B$.
2. Transition & Range Updates: As we iterate the active index from $2$ to $N$, the contribution of $B[i-1]$ shifts. This transformation corresponds exactly to adding $B[i-1]$ to specific subsegments and modifying the individual boundary element. These updates are performed efficiently in $O(\log N)$ using range addition updates.
3. Query: After updating the tree for each step, the global optimum is simply the maximum/minimum value at the root of the Segment Tree (query(1, 1, n, 1, n)), allowing us to maintain the overall running answer.

Complexity: - Time Complexity: $O(N \log N)$ since we perform a constant number of Segment Tree operations for each of the $N$ steps. - Space Complexity: $O(N)$ to store the arrays and the tree structures.