Monday, October 27, 2014

Data Structure for Frequent Range Updates

Given an update operation as following: from index i to index j, we add p to each array[i]. What kind of data structure that can support this operation efficiently?

Of course segment tree and fenwick tree does this well in \(O(N\lg{N})\) complexity for building the tree, \(O(\lg{N})\) for updates (insertion), and \(O(\lg{N})\) for processing search queries. However, what if we have a use case where we do updates very very frequently, like 99% of the time?

Two days ago I've discovered this data structure while reading on some people's code, and I'm not really sure whether there is a standard way to call it. The data structure I am about to present here does the updates in O(1) (yeap) but to do a search query we have at worst O(N) at each time. But the simplicity is really striking.

We use an array to keep track on the updates information, call this mark[]. For each updates in the form of (p, i, j), we do:
1. mark[j] += p
2. mark[i-1] -= p
And this information suffices to show that we intent to add p to each and every cell in i to j.

How do we process the information when we need to do a retrieval of data? Once the need arise, we do a one sweep operation from i = N to 1: mark[i-1] += mark[i]
Then each mark[i] represent how much values we already added to element i throughout the updating process!