I need a DS to support the following operations efficiently:

- Find Sum of some contiguous block [l,r].
- Find Max of some contiguous block [l,r].
- Insert an item in sorted order

First 2 ops can be implemented well using segment trees but how to exactly mimic the insertions.

Also, this needs to work “online”.

I don’t want to augment any self balancing tree.

**Clarification** : The data to be maintained is actually a list of objects. It will be sorted in terms of data.a, sum request in terms of data.b, and maximums for data.c.