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.