let $$$g_i$$$ be the rightmost $$$j < i$$$ such that $$$a_j > a_i$$$ (or 0 if it doesn't exist.) we know how to calculate $$$g$$$ using a stack. now, we know that $$$seg_j = f_j + max(a_{j+1},\cdots,a_{i-1})$$$, and we want to update it such that $$$seg_j = f_j + max(a_{j+1},\cdots,a_i)$$$. it's easy to see the values of $$$seg_j (j \leq g_i)$$$ won't change.

let's look at indexes $$$g_i < j < i$$$:
- for $$$g_{i-1} < j \leq i-1$$$, $$$seg_j = f_j + a_{i-1}$$$, but it should be $$$f_j + a_i$$$
- for $$$g_{g_{i-1}} < j \leq g_{i-1}$$$, $$$seg_j = f_j + a_{g_{i-1}}$$$, but it should be $$$f_j + a_i$$$
- for $$$g_{g_{g_{i-1}}} < j \leq g_{g_i}$$$, $$$seg_j = f_j + a_{g_{g_{i-1}}}$$$, but it should be $$$f_j + a_i$$$
- and so on.
as we can see, the segment $$$[g_i+1 , i)$$$ is divided into several subsegments, such that we need to add the same number to all values in the same subsegment to update values of our segment tree.finally, we should set $$$seg_i$$$ to $$$f_i$$$. here is a pseudo code:

   let j be i-1
   while j > g[i] do :
     add a[i]-a[j] to (g[j] , j]
     j = g[j]
   calculate f[i]
   add f[i] to [i,i]