Performing queries to find the triangle with the largest perimeter from an array of given side.

Question

We are given an array of numbers.We will be performing 2 types of querier:-

1)Find the triangle with the maximum perimeter in a given interval (l,r).
2)Update the array element at the given index i to a new given value x.

Example:-

1. We are given a[] = 3,1,8,9,7.We will be performing 4(q) queries in total.The first query is to find the maximum perimeter in the interval (1,5).So, we would return 24 as the maximum possible perimeter of the triangle in the range (1,5) is 24(8+9+7).
2. The second query is to update the value at index 2 to 12.So, now our array becomes a[] = 3,12,8,9,7.
3. The third query is to find the maximum perimeter in the interval (1,3) i.e from the array elements 3,1,8.We can't form any triangle from these elements.Hence, we return 0.

---

Now I have come up with an O(q*nlogn) approach by first sorting the elements for each query but was wondering if there is another better way.I was thinking of applying square root decomposition or segment trees but am not sure.