1
$\begingroup$

I need to come up with a data structure that supports the following interface:

  • new(time_stamp x, value v): insert a new data v for time stamp x
  • update(time_stamp x, value v): update the data for time stamp x to v
  • delete(time_stamp x): delete the data for time stamp x
  • query(time_stamp x): returns sum of all data whose time stamp is less than or equal to x

The data structure needs to support out of sequence data. I need the query operation to run in O(1) time. While there is no restriction for other provided interfaces, I don't want to end up with O(n) time complexity for any of them.

An AVL tree seems a good candidate, however I'm not aware of any technique (maybe amortized cost analysis) to reduce the O(log n) query complexity for AVL tree to O(1).

I appreciate any suggestion or direction toward implementing such a data structure.

$\endgroup$
  • $\begingroup$ Seems like it requires some sort of persistence/retroactive data structure? $\endgroup$ – BearAqua Mar 25 at 21:41
  • $\begingroup$ @D.W. Thanks for your edits. I have no guarantee that all these requirements are achievable or not. The following paper *LOGARITHMIC LOWER BOUNDS IN THE CELL-PROBE MODEL∗, suggests the new lower bound of Ω(log n) for dynamic trees. This is a simplified version of an order handler, which query operation is the most time-sensitive operation. $\endgroup$ – Alireza Majidi Mar 25 at 21:53
  • $\begingroup$ @bearaqua Sorry for that, I meant AVL tree. I updated the question. $\endgroup$ – Alireza Majidi Mar 25 at 21:57
  • 1
    $\begingroup$ I doubt that your requirements are achievable, but I don't have a proof of that. It is not hard to achieve $O(\log n)$ running time for all four operations (e.g., AVL trees suffice, as you hint, if you augment each node with a sum of all values below it), but I don't see how to achieve $O(1)$-time query if you want all other operations to take $o(n)$ time. $\endgroup$ – D.W. Mar 26 at 0:04
  • 1
    $\begingroup$ Van Emde Boas tree has better complexity on all the operations(O(log log n)). Still not possible to achieve O(1) time complexity. $\endgroup$ – James Parker Mar 26 at 10:19
1
$\begingroup$

If the timestamps can take $T$ different values, then it is simple to implement the new, update, and delete operations in time $\Theta(T)$ and the query in time $O(1)$, by maintaining two arrays $val[ ]$ and $q[]$ of size $T$. The array $q[]$ is initially filled with zero values.

  • new(x, v): set $val[x] = v$ and increment each $q[y]$ with $y\ge x$ by $v$;
  • update(x, v): let $v' = val[x]$; increment each $q[y]$ with $y \ge x$ by $v-v'$, then set $val[x]=v$;
  • delete(x, v): let $v' = val[x]$; decrement each $q[y]$ with $y \ge x$ by $v'$;
  • query(x): return $q[x]$.

Note that $n$ (number of data items, that is, the number of total calls to new) is unrelated to $T$ (range of the timestamps). Whenever $T=o(n)$, the above implementation satisfies your requirements. For example, if a timestamp is a day of the year, $T$ will be a constant, even though $n$ can be arbitrarily large (because you can have arbitrarily many new and deletes).

If, on the other hand, $T$ can be larger than $n$, then as D.W. noted in his comment your requirements may be too strict.

$\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.