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.