||you can do that with that is called "late update".
you update segments as it4.kp suggested, and when there is a max query, you resolve what you have saved in those additional fields. But you should resolve only those which are related, so you get logn for both queries.(since you can resolve at most 2 with MAX query)
Also, while resolving, don't do unneccessary resolve operations. for example, if you are going to resolve the additional field of [i,i+k] for a query like [i,i+5] and [i,i+5] is included in the [i,i+k/2] part, then just pump the additional value to both childs of [i,i+k] (namely [i,i+k/2] and [i+k/2+1 , i+k]) and resolve [i,i+k/2] part because you only need that part.