# Constant time range sum query

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.

• Seems like it requires some sort of persistence/retroactive data structure? – BearAqua Mar 25 at 21:41
• @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. – Alireza Majidi Mar 25 at 21:53
• @bearaqua Sorry for that, I meant AVL tree. I updated the question. – Alireza Majidi Mar 25 at 21:57
• 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. – D.W. Mar 26 at 0:04
• Van Emde Boas tree has better complexity on all the operations(O(log log n)). Still not possible to achieve O(1) time complexity. – James Parker Mar 26 at 10:19

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.