Constant time range sum query

Question

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.

Answer 1

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.