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
0 comments:
Post a Comment
Let us know your responses and feedback