SuperJ6's blog

Subarray Sorting Queries DS
By SuperJ6, history, 4 years ago, In English

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.

  • Vote: I like it
  • +36
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Can you be more accurate about what you want or give an example? To me, "sorting subarrays" is pretty vague (assuming you don't want to literally list all subarrays sorted per query)

→ Reply
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Interesting problem, I am also curious.

→ Reply
»
4 years ago, # |
  Vote: I like it +32 Vote: I do not like it

See here.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Thank you! That's definitely where I saw it, I can't believe I couldn't find/remember it was there, I was just on that page today smh.

    → Reply