Pat Morin

Consider the data structuring problem of maintaining a sequence A_1,...,A_n of integers with each A_i in {1,...,n} under the following two operations:

- Modify(i, x) : Set A_i = x (update)
- PartialSum(i) : Compute the sum of A_1,...,A_i (query)

In this talk we will present a recent result due to Demaine and Patrascu (SICOMP 2006) which shows that the above data structure is optimal. There exists sequences of O(n) updates and searches that require Omega(n log n) time. This lower bound holds in the cell probe model of computation in which the only cost associated with an algorithm are these costs of reading and writing individual memory cells.