14
$\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.

Improve this question
$\endgroup$
9
  • $\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$
    – J..y B..y
    Commented Apr 12, 2013 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
    Commented Apr 12, 2013 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
    Commented Apr 12, 2013 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$
    – J..y B..y
    Commented Apr 15, 2013 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
    Commented Apr 15, 2013 at 12:17

2 Answers 2

Reset to default
3
$\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.

Improve this answer
$\endgroup$
4
  • $\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
    Commented May 8, 2015 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
    Commented May 8, 2015 at 15:44
  • $\begingroup$ Could you give an example? $\endgroup$
    – jbapple
    Commented May 8, 2015 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
    Commented May 8, 2015 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.

Improve this answer
$\endgroup$
1
  • $\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
    Commented Apr 7, 2015 at 16:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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