Subarray Sorting Queries DS

Revision en2, by SuperJ6, 2020-04-23 02:56:17

I was wondering if there is any data structure for supporting editing elements, querying elements, and sorting sub-arrays, faster than the naive implementation.

For example, consider the starting array [3, 5, 2, 6, 9, 5, 1]. For a query, you want to sort the subarray between indices 1 and 5 (0 index inclusive). You are left with resulting array [3, 2, 5, 5, 6, 9, 1]. Now you want to query for element at index 4, which you print 6. Now query to change index 4 to 3 and query to print it, and you print 3.

Essentially you are supposed to maintain idea you are sorting so that you print correct element at index, but you don't want to actually sort the whole subarray every time obviously.

I thought I remembered hearing something about this, but can't find any resources so maybe i just made the idea it's possible up.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English SuperJ6 2020-04-23 02:56:17 550
en1 English SuperJ6 2020-04-23 01:57:13 306 Initial revision (published)