As the title says, there are these two types of queries. number of values (n) <= 100000 and number of queries <= 200000, the solution that came to my mind is using a segment tree, where each node of the segment tree is an AVL tree that stores the elements of the segment tree node interval in ascending order, and each node of any AVL tree will store the sum of elements of the subtree rooted at this node.

So if I need to update an element (write a new value to it), I go to the segment tree nodes whose intervals contain the position of the element (log(n) nodes) and update the AVL tree of each of these nodes (each update is log(n)), so in total (log(n))^2.

And if I want sum of numbers less than x in interval l to r, I do a query operation so that when the segment tree node is totally inside l to r, I use the AVL tree of this node to get sum of elements less than x in log(n) complexity, and the higher level segment tree nodes will return the summation of these lower level segment tree nodes' sums (so in total (log(n))^2).

If number of queries/updates is Q, their complexity becomes Q*(log(n))^2. am I walking in the right path or is there something wrong in this approach ?