×

# Suggest a Suitable DS

 0 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. asked 10 Jun '13, 16:39 1.1k●13●22●29 accept rate: 0%

 0 @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 12.4k●47●107●171 accept rate: 12% Clarification done. (10 Jun '13, 18:21)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,726
×1,385

question asked: 10 Jun '13, 16:39

question was seen: 1,290 times

last updated: 10 Jun '13, 18:21