We want to have a data structure that allows us to do two things
- Make queries of the form
f(a[i], ..., a[j])
fori <= j
(the query) - Update
a[i] = v
for somei
(the update)
Naively, one could do this in such a way that either the query or the update is O(1)
and the other is O(n)
. The most basic method would be to simply store a[i]
and then for the query, simply compute the function in O(n)
. However, that will obviously not be good enough for practical applications.