I need a DS to support the following operations efficiently:
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. asked 10 Jun '13, 16:39

@code_master01 : You are saying operation 3 is insert in sorted order . Does that mean the list you keep is sorted . In that case operation 2 becomes trivial . If you have to maintain an arbitrary list ( unsorted ) and do some update operations and retrieve max in an interval then you can use Fenwick tree ( read topcoder tutorial on it or wikipedia entry ) or you can use square root decomposition . Please clarify you question as it is currently unclear . answered 10 Jun '13, 16:51
