I have an array A of N elements (1 <= N <= 200000). Now I have Q (1 <= Q <= 200000) queries. In each query, 3 integers x, l and r are given. I have to find min{x*j + A[j]} where l <= j <= r. I was thinking about solving this by segment tree or dynamic programming but still I can't handle proper time complexity. Example: Input Array A = [12, 13, 33, 25, 10, 41, 51, 2]. Query: 2 1 5 Output: 14 Query: 5 5 8 Output: 35. Can anybody tell me the right approach?
minimum convex hull trick in every vertex of segment tree
O(NlogN2).
Thank you. Can you give me any resources for that?
search "convex hull trick" in google
Link This might help. Also can you share the problem code which you are solving?