Problem Detail: We are given an array $A[1..n]$ of integers, and an array of 3-tuples known as queries. The query tuples $(i,j,v)$ denote additions of an integer $v$ to the subarray of $A[i..j]$. I’m interested in the query time of $A[k]$ for $1 leq k leq n$ between the queries. For example, let $A = [1,2,3,4]$, and let the queries be $Q = [[1,2,5],[2,3,6],[1,3,10]]$. After the second query has been processed, say I want to find the value of $A[3]$, which would be $3+5+6=14$. Does an algorithm exists to do this in less than linear time?
Asked By : mohammed essam
Answered By : D.W.
Yes, there are good data structures for this. The running time to handle $q$ queries and $ell$ lookups will be $O((q+ell) lg n)$ time in total, or in other words, $O(lg n)$ time per query and $O(lg n)$ time per lookup. This can be much faster than linear time in general. Let $A_text{orig}[1..n]$ denote the original value of the array $A$. We’re going to build a data structure to represent the array $Delta[1..n]$ of integers, where $Delta[i]$ holds the amount that $A[i]$ has been increased by (given the queries so far). Thus, to compute $A[i]$, it suffices to look up $A_text{orig}[i]$ and $Delta[i]$ and return their sum. The question is, how do we maintain the $Delta[]$ array in a way that we can efficiently look up $Delta[i]$ at any index $i$, and that we can efficiently update $Delta$ in response to a particular query? If we represent $Delta$ as an array, then lookups take $O(1)$ time, but updates (handling a query) may take $Theta(n)$ time, which is no good. A better solution is to represent $Delta$ using an interval tree. With the proper data structures, each lookup will take $O(lg n)$ time, and each update (processing each query) will take $O(lg n)$ time. This should give an efficient algorithm. An interval tree holds a set of non-overlapping intervals. In our case, the intervals will be consecutive ranges of array indices for which $Delta$ holds the same value. We will augment the data structure to hold the value of $Delta$ for each such interval. For example, initially the interval tree could be represented as $[1,n] mapsto 0$, to represent that all indices in the interval $[1,n]$ yield the value 0; so $Delta[i]=0$ for all $i$. If we now receive the query $(1,2,5)$, then $Delta$ is updated to the interval tree $[1,2] mapsto 5, [3,n] mapsto 0$. If we then receive the query $(2,5,6)$, then the interval tree should be updated to $[1,1] mapsto 5, [2,2] mapsto 11, [3,5] mapsto 6, [6,n] mapsto 0$. We can store the interval tree using a binary search tree. If we have $m$ intervals, then there will be at most $2m$ unique endpoints of the intervals. We store these endpoints in a binary search tree. Each leaf node represents a single endpoint. We will augment the nodes with a value: if a node represents the integer $a$ (an array index) and the next-largest integer endpoint is $b$, then the value $v$ at the node for $a$ means that the interval tree contains $[a,b-1] mapsto v$. Note that each query can be processed in $O(lg n)$ time. That’s because a query might possibly split two existing intervals in the tree into two sub-intervals. Each split operation can be handled in $O(lg n)$ time by inserting one node into the binary search tree. Similarly, lookups can be handled in $O(lg n)$ time, by traversing the binary search tree to find the largest node that is less than or equal to the index you’re looking up. This provides a sub-linear time solution to your problem. Processing $q$ queries and $ell$ lookups to the array takes $O((q+ell) lg n)$ time in total.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/11777 3.2K people like this
