# Data structure for updates on intervals and querying number of zeros

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.

• 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). – Jeremy Apr 12 '13 at 8:48
• 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. – Chao Xu Apr 12 '13 at 17:46
• 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. – Christoph Dürr Apr 12 '13 at 21:38
• 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)$. – Jeremy Apr 15 '13 at 7:22
• Here is a nice link where you can test your implementations against other solutions to the same problem: spoj.com/OI/problems/NKMARS – Erel Segal-Halevi Apr 15 '13 at 12:17

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.

• 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$? – jbapple May 8 '15 at 13:52
• 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. – David Eppstein May 8 '15 at 15:44
• Could you give an example? – jbapple May 8 '15 at 23:01
• 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 – David Eppstein May 8 '15 at 23:34

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.

• 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. – S. Pek Apr 7 '15 at 16:57