0
$\begingroup$

I have a sequence. And now for each element in this sequence I would like to know how many subsequent elements are larger. Or, in other words, I have a sequence $a_1, \ldots, a_n$, and for each $1\leq i\leq n$ I would like to compute $|\lbrace j|j>i\wedge a_j > a_i\rbrace|$.

My idea: Implement an AVL tree, put elements from this sequence to this AVL tree from the last one to the first one. Before putting each element obtain the amount of larger elements the tree already contains. I can implement an AVL tree that would allow such operations.

But alas, I do have to implement such an AVL tree, since unfortunately the standard C++ std::set doesn't allow obtaining the distance between two iterators in logarithmic time.

Now I need this to solve a task from one of the former exams on algorithms and data structures. These exams usually contain two tasks, a "simpler" one and a "harder" one. And this is the "simpler" one. Now I doubt that a "simpler" task would require implementing an AVL tree. A "harder" task might; but a "simpler" one, doubtfully. Therefore, I would say, there should be a less laborious way to solve this task.

Is there any simpler way to compute what I need to compute?

$\endgroup$
  • $\begingroup$ It may help to sort the sequence and look at the difference in indexes of the same element in the sorted sequence vs the original sequence. $\endgroup$ – Discrete lizard Jan 17 '18 at 11:00
0
$\begingroup$

You can use any balanced binary search tree data structure (doesn't have to be AVL tree). Some such data structures are easier to implement (maybe a AA tree, left-leaning red-black tree, or splay tree?). If you don't care about worst-case running time, it doesn't need to be balanced. One pragmatic solution might be to use skip lists.

Are you sure the exam required students to implement their solution? In my experience, exams in the algorithms and data structure courses I'm familiar with rarely require implementing the solution -- it is enough to describe the solution clearly. A solution based on augmenting an AVL tree can be described in a fairly simple way: you say "take a AVL tree, and modify it in such-and-such a way", and that doesn't require re-describing all the details of how AVL trees work. Only you know what the typical expectations are for the kind of exam you are looking at.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.