The problem is: Given an array of 10^5 numbers and 10^5 queries, each query is like "i j" means: find the largest possible value A[y]-A[x] such that i<=x<=y<=j.
The analysis of this problem said it is easy to do with segment tree, but I have no idea, can anyone please explain how? (btw, it also has update operation, otherwise I could do it with offline semgment tree)
Thanks in advance!