13
$\begingroup$

I am looking for a data structure that would maintain an integer table $t$ of size $n$, and allowing the following operations in time $O(\log n)$.

  • $\text{increase}(a,b)$, which increases $t[a],t[a+1],\ldots,t[b]$.
  • $\text{decrease}(a,b)$, which decreases $t[a],t[a+1],\ldots,t[b]$.
  • $\text{support}()$, which returns the number of indices $i$ such that $t[i]\neq 0$.

You have the promise that every call to decrease can be matched to a previous call to increase with the same parameters $a,b$. The application I have in mind is a sweepline algorithm to compute in time $O(n\log n)$ the area of the union of n given rectilinear rectangles.

A quad-tree would have size $\Theta(n^2)$, so it is not a solution. Fenwick or Interval trees have the right flavor, but I don't see how to extend them to support the operations above.

$\endgroup$
  • $\begingroup$ Fenwick trees would not use the promise that "every call to decrease can be matched to a previous call to increase with the same parameters a,b", so there might be a simpler solution using that promise (but it escapes me for now). $\endgroup$ – Jeremy Apr 12 '13 at 8:48
  • $\begingroup$ Since the number of input you can have is at most $n^2$(you can detect repeats and not insert into the data structure), we still get $O(\log n)$ performance using the common measure tree data structure. See cosy.sbg.ac.at/~ksafdar/data/courses/SeminarADS/… slide 47-52. $\endgroup$ – Chao Xu Apr 12 '13 at 17:46
  • $\begingroup$ Jérémie and Chao Xu. Thank for your comments. I understand now how the Interval Tree can be used to maintain the total length of the union of a changing set of intervals. This is in fact a very cute datastructure. $\endgroup$ – Christoph Dürr Apr 12 '13 at 21:38
  • $\begingroup$ For the general data structure problem, searching in $\log(n^2)\in O(\log(n))$ time requires space $O(p)\subset O(n^2)$ where $p$ is the size of the list of active pairs of coordinates. But indeed for the sweepline algorithm $p\in O(n)$ so the space stays linear. The problem is still open for a data structure with better space than $O(p)$, when $p\in\omega(n)$. $\endgroup$ – Jeremy Apr 15 '13 at 7:22
  • 2
    $\begingroup$ Here is a nice link where you can test your implementations against other solutions to the same problem: spoj.com/OI/problems/NKMARS $\endgroup$ – Erel Segal-Halevi Apr 15 '13 at 12:17
2
$\begingroup$

Use a segment tree — a recursive partition of the range $[1,n]$ into smaller ranges. Each interval $[a,b]$ of your update operations can be partitioned into $O(\log n)$ of the ranges in this recursive partition. For each range $[x,y]$ store:

  • The number $c(x,y)$ of intervals $[a,b]$ that have been increased and not decreased such that $[x,y]$ is one of the ranges into which $[a,b]$ is partitioned
  • The number $u(x,y)$ of cells that are not covered by partitioned subsets of intervals that are at $[x,y]$ or lower in the recursion

Then if $[x,y]$ is recursively split into $[x,z]$ and $[z+1,w]$ we have $$u(x,y)=\begin{cases} 0&\text{if }c(x,y)>0\\ u(x,z)+u(z+1,y)&\text{otherwise} \end{cases}$$ so we can update each $u(x,y)$ value in constant time when the other data for a range changes. Each support query can be answered by looking at $u(1,n)$.

To perform an increase$(a,b)$ operation, partition $[a,b]$ into $O(\log n)$ ranges, increment $c(x,y)$ for each of these ranges, and use the formula above to recalculate $u(x,y)$ for each of these ranges and each of their ancestors. The decrease operation is the same with a decrement instead of an increment.

$\endgroup$
  • $\begingroup$ I don't think I understand your second bullet. In the subtree with rot labeled $[x,y]$, which cells are not covered by partitioned subsets of intervals at $[x,y]$? Isn't the whole range $[x,y]$ covered, so $u(x,y) = 0$? $\endgroup$ – jbapple May 8 '15 at 13:52
  • $\begingroup$ It depends on which increase operations you have made. Initially all of them are uncovered, but when you increase a small interval within $[x,y]$ (or any interval that starts or ends within $[x,y]$, or that includes $[x,y]$ in its partition) it decreases. $\endgroup$ – David Eppstein May 8 '15 at 15:44
  • $\begingroup$ Could you give an example? $\endgroup$ – jbapple May 8 '15 at 23:01
  • $\begingroup$ Suppose your interval is the numbers [1,8]. It is recursively divided into [1,4], [4,8], then [1,2], [3,4], [5,6], and [7,8], then all one-element ranges. Initially, everything is uncovered, all c[x,y]=0, and each range has u=its length. But then, suppose you perform an increase[2,6] operation. The O(log n) maximal ranges into which [2,6] can be decomposed are [2,2], [3,4], and [5,6], so we set c[x,y] for those three ranges to 1. According to the formula in my answer, this causes u[x,y] for these three ranges to also become 0. u[1,2] becomes 1, u[1,4] also becomes 1, u[5,8]=2, and u[1,8]=1+2=3 $\endgroup$ – David Eppstein May 8 '15 at 23:34
0
$\begingroup$

You can support $\text{increase}$ and $\text{decrease}$ in $O(\sqrt{n}\log n)$ and $\text{support}$ in $O(1)$ time. The key idea is to break up the table into groups of size $\Theta(\sqrt{n})$. Then each modifying operation ($\text{increase}$ or $\text{decrease}$) operates on at most $O(\sqrt{n})$ groups, and only the ones near the end of its range ($a$ and $b$, in your formulation) take $\omega(\log n)$ time.

$\endgroup$
  • $\begingroup$ Why not take this approach to the limit. Instead of bucketing into $O(\sqrt{n})$ buckets, we can instead form a tree similar to this: 1 / \ 2 3 / \ / \ 4 5 6 7 Of which, by updating, you take $O(\log{n})$ for all operations. $\endgroup$ – S. Pek Apr 7 '15 at 16:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.