Suggest a Suitable DS

general
,
1

I need a DS to support the following operations efficiently:

  1. Find Sum of some contiguous block [l,r].
  2. Find Max of some contiguous block [l,r].
  3. 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.

2

@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 .

3

Clarification done.