You are not logged in. Please login at www.codechef.com to post your questions!

×

Suggest a Suitable DS

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.

asked 10 Jun '13, 16:39

code_master01's gravatar image

5★code_master01
1.1k132229
accept rate: 0%

edited 10 Jun '13, 18:20


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

link

answered 10 Jun '13, 16:51

vineetpaliwal's gravatar image

6★vineetpaliwal
12.4k47107170
accept rate: 12%

Clarification done.

(10 Jun '13, 18:21) code_master015★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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,264
×1,140

question asked: 10 Jun '13, 16:39

question was seen: 1,071 times

last updated: 10 Jun '13, 18:21